Given a tree having every node’s value as either 0 or 1, the task is to find the maximum size of the sub-tree in the given tree that has equal number of 0’s and 1’s, if no such sub-tree exists then print -1.
Examples:
Input:
Output: 6
Input:
Output: -1
Approach:
- Change all the nodes of the tree which are 0 to -1. Now the problem gets reduced to finding the maximum size of a sub-tree sum of whose nodes is 0.
- Update all the nodes of the tree so that they represent the sum of all nodes in the sub-tree rooted at the current node.
- Now find the size of the maximum sub-tree rooted at a node whose value is 0. If no such node is found then print -1
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <iostream>using namespace std;// To store the size of the maximum sub-tree// with equal number of 0's and 1'sint maxSize = -1;// Represents a node of the treestruct node { int data; struct node *right, *left;};// To create a new nodestruct node* newnode(int key){ struct node* temp = new node; temp->data = key; temp->right = NULL; temp->left = NULL; return temp;}// Function to perform inorder traversal on// the tree and print the nodes in that ordervoid inorder(struct node* root){ if (root == NULL) return; inorder(root->left); cout << root->data << endl; inorder(root->right);}// Function to return the maximum size of// the sub-tree having equal number of 0's and 1'sint maxsize(struct node* root){ int a = 0, b = 0; if (root == NULL) return 0; // Max size in the right sub-tree a = maxsize(root->right); // 1 is added for the parent a = a + 1; // Max size in the left sub-tree b = maxsize(root->left); // Total size of the tree // rooted at the current node a = b + a; // If the current tree has equal // number of 0's and 1's if (root->data == 0) // If the total size exceeds // the current max if (a >= maxSize) maxSize = a; return a;}// Function to update and return the sum// of all the tree nodes rooted at// the passed nodeint sum_tree(struct node* root){ if (root != NULL) // If current node's value is 0 // then update it to -1 if (root->data == 0) root->data = -1; int a = 0, b = 0; // If left child exists if (root->left != NULL) a = sum_tree(root->left); // If right child exists if (root->right != NULL) b = sum_tree(root->right); root->data += (a + b); return root->data;}// Driver codeint main(){ struct node* root = newnode(1); root->right = newnode(0); root->right->right = newnode(1); root->right->right->right = newnode(1); root->left = newnode(0); root->left->left = newnode(1); root->left->left->left = newnode(1); root->left->right = newnode(0); root->left->right->left = newnode(1); root->left->right->left->left = newnode(1); root->left->right->right = newnode(0); root->left->right->right->left = newnode(0); root->left->right->right->left->left = newnode(1); sum_tree(root); maxsize(root); cout << maxSize; return 0;} |
Java
// Java implementation of the approachclass GFG{// To store the size of the maximum sub-tree// with equal number of 0's and 1'sstatic int maxSize = -1;// Represents a node of the treestatic class node { int data; node right, left;};// To create a new nodestatic node newnode(int key){ node temp = new node(); temp.data = key; temp.right = null; temp.left = null; return temp;}// Function to perform inorder traversal on// the tree and print the nodes in that orderstatic void inorder(node root){ if (root == null) return; inorder(root.left); System.out.print(root.data +"\n"); inorder(root.right);}// Function to return the maximum size of// the sub-tree having equal number of 0's and 1'sstatic int maxsize(node root){ int a = 0, b = 0; if (root == null) return 0; // Max size in the right sub-tree a = maxsize(root.right); // 1 is added for the parent a = a + 1; // Max size in the left sub-tree b = maxsize(root.left); // Total size of the tree // rooted at the current node a = b + a; // If the current tree has equal // number of 0's and 1's if (root.data == 0) // If the total size exceeds // the current max if (a >= maxSize) maxSize = a; return a;}// Function to update and return the sum// of all the tree nodes rooted at// the passed nodestatic int sum_tree(node root){ if (root != null) // If current node's value is 0 // then update it to -1 if (root.data == 0) root.data = -1; int a = 0, b = 0; // If left child exists if (root.left != null) a = sum_tree(root.left); // If right child exists if (root.right != null) b = sum_tree(root.right); root.data += (a + b); return root.data;}// Driver codepublic static void main(String[] args){ node root = newnode(1); root.right = newnode(0); root.right.right = newnode(1); root.right.right.right = newnode(1); root.left = newnode(0); root.left.left = newnode(1); root.left.left.left = newnode(1); root.left.right = newnode(0); root.left.right.left = newnode(1); root.left.right.left.left = newnode(1); root.left.right.right = newnode(0); root.left.right.right.left = newnode(0); root.left.right.right.left.left = newnode(1); sum_tree(root); maxsize(root); System.out.print(maxSize);}}// This code is contributed by PrinciRaj1992 |
Python3
# Python implementation of the approach # To store the size of the maximum sub-tree# with equal number of 0's and 1'smaxSize = -1# Represents a node of the treeclass Node: def __init__(self, val = 0): self.data = val self.left = None self.right = None # To create a new nodedef newnode(key): temp = Node() temp.data = key temp.right = None temp.left = None return temp# Function to perform inorder traversal on# the tree and print the nodes in that orderdef inorder( root): if (root == None): return inorder(root.left) print(root.data) inorder(root.right)# Function to return the maximum size of# the sub-tree having equal number of 0's and 1'sdef maxsize(root): global maxSize a,b = 0,0 if (root == None): return 0 # Max size in the right sub-tree a = maxsize(root.right) # 1 is added for the parent a = a + 1 # Max size in the left sub-tree b = maxsize(root.left) # Total size of the tree # rooted at the current node a = b + a # If the current tree has equal # number of 0's and 1's if (root.data == 0): # If the total size exceeds # the current max if (a >= maxSize): maxSize = a return a# Function to update and return the sum# of all the tree nodes rooted at# the passed nodedef sum_tree(root): if (root != None): # If current node's value is 0 # then update it to -1 if (root.data == 0): root.data = -1 a,b = 0,0 # If left child exists if (root.left != None): a = sum_tree(root.left) # If right child exists if (root.right != None): b = sum_tree(root.right) root.data += (a + b) return root.data# Driver coderoot = newnode(1)root.right = newnode(0)root.right.right = newnode(1)root.right.right.right = newnode(1)root.left = newnode(0)root.left.left = newnode(1)root.left.left.left = newnode(1)root.left.right = newnode(0)root.left.right.left = newnode(1)root.left.right.left.left = newnode(1)root.left.right.right = newnode(0)root.left.right.right.left = newnode(0)root.left.right.right.left.left = newnode(1)sum_tree(root)maxsize(root)print(maxSize)# This code is contributed by shinjanpatra |
C#
// C# implementation of the approachusing System;class GFG{// To store the size of the maximum sub-tree// with equal number of 0's and 1'sstatic int maxSize = -1;// Represents a node of the treepublic class node { public int data; public node right, left;};// To create a new nodestatic node newnode(int key){ node temp = new node(); temp.data = key; temp.right = null; temp.left = null; return temp;}// Function to perform inorder traversal on// the tree and print the nodes in that orderstatic void inorder(node root){ if (root == null) return; inorder(root.left); Console.Write(root.data +"\n"); inorder(root.right);}// Function to return the maximum size of// the sub-tree having equal number of 0's and 1'sstatic int maxsize(node root){ int a = 0, b = 0; if (root == null) return 0; // Max size in the right sub-tree a = maxsize(root.right); // 1 is added for the parent a = a + 1; // Max size in the left sub-tree b = maxsize(root.left); // Total size of the tree // rooted at the current node a = b + a; // If the current tree has equal // number of 0's and 1's if (root.data == 0) // If the total size exceeds // the current max if (a >= maxSize) maxSize = a; return a;}// Function to update and return the sum// of all the tree nodes rooted at// the passed nodestatic int sum_tree(node root){ if (root != null) // If current node's value is 0 // then update it to -1 if (root.data == 0) root.data = -1; int a = 0, b = 0; // If left child exists if (root.left != null) a = sum_tree(root.left); // If right child exists if (root.right != null) b = sum_tree(root.right); root.data += (a + b); return root.data;}// Driver codepublic static void Main(String[] args){ node root = newnode(1); root.right = newnode(0); root.right.right = newnode(1); root.right.right.right = newnode(1); root.left = newnode(0); root.left.left = newnode(1); root.left.left.left = newnode(1); root.left.right = newnode(0); root.left.right.left = newnode(1); root.left.right.left.left = newnode(1); root.left.right.right = newnode(0); root.left.right.right.left = newnode(0); root.left.right.right.left.left = newnode(1); sum_tree(root); maxsize(root); Console.Write(maxSize);}}// This code is contributed by Rajput-Ji |
Javascript
<script>// JavaScript implementation of the approach // To store the size of the maximum sub-tree // with equal number of 0's and 1's var maxSize = -1; // Represents a node of the tree class Node { constructor(val) { this.data = val; this.left = null; this.right = null; } } // To create a new node function newnode(key) { var temp = new Node(); temp.data = key; temp.right = null; temp.left = null; return temp; } // Function to perform inorder traversal on // the tree and print the nodes in that order function inorder( root) { if (root == null) return; inorder(root.left); document.write(root.data + "\n"); inorder(root.right); } // Function to return the maximum size of // the sub-tree having equal number of 0's and 1's function maxsize( root) { var a = 0, b = 0; if (root == null) return 0; // Max size in the right sub-tree a = maxsize(root.right); // 1 is added for the parent a = a + 1; // Max size in the left sub-tree b = maxsize(root.left); // Total size of the tree // rooted at the current node a = b + a; // If the current tree has equal // number of 0's and 1's if (root.data == 0) // If the total size exceeds // the current max if (a >= maxSize) maxSize = a; return a; } // Function to update and return the sum // of all the tree nodes rooted at // the passed node function sum_tree( root) { if (root != null) // If current node's value is 0 // then update it to -1 if (root.data == 0) root.data = -1; var a = 0, b = 0; // If left child exists if (root.left != null) a = sum_tree(root.left); // If right child exists if (root.right != null) b = sum_tree(root.right); root.data += (a + b); return root.data; } // Driver code var root = newnode(1); root.right = newnode(0); root.right.right = newnode(1); root.right.right.right = newnode(1); root.left = newnode(0); root.left.left = newnode(1); root.left.left.left = newnode(1); root.left.right = newnode(0); root.left.right.left = newnode(1); root.left.right.left.left = newnode(1); root.left.right.right = newnode(0); root.left.right.right.left = newnode(0); root.left.right.right.left.left = newnode(1); sum_tree(root); maxsize(root); document.write(maxSize);// This code contributed by aashish1995</script> |
Output:
6
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
