Check if the given binary tree has a sub-tree with equal no of 1’s and 0’s | Set 2
Given a tree having every node’s value as either 0 or 1, the task is to find whether the given binary tree contains any sub-tree that has equal number of 0’s and 1’s, if such sub-tree is found then print Yes else print No.
Examples:
Input:
Output: Yes
There are two sub-trees with equal number of 1’s and 0’s.
Hence the output is “Yes”
Input:
Output: No
Approach:
- Update all the nodes of the tree so that they represent the sum of all the nodes in the sub-tree rooted at the current node.
- Now if some node exists whose value is half of the number of nodes in the tree rooted at the same node then it is a valid sub-tree.
- If no such node exists then print No.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <iostream>using namespace std;// To store whether the tree contains a sub-tree// with equal number of 0's and 1'sbool hasValidSubTree = false;// 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 size of the// sub-tree rooted at the current nodeint size(struct node* root){ int a = 0, b = 0; // If root is null or the valid sub-tree // has already been found if (root == NULL || hasValidSubTree) return 0; // Size of the right sub-tree a = size(root->right); // 1 is added for the parent a = a + 1; // Size of the left sub-tree b = size(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 (a % 2 == 0 && root->data == a / 2) hasValidSubTree = true; 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) return 0; 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(1); root->left->right->right->left->left = newnode(1); sum_tree(root); size(root); if (hasValidSubTree) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation of the approach import java.util.Comparator;class GFG{// To store whether the tree contains a sub-tree // with equal number of 0's and 1's static boolean hasValidSubTree = false; // Represents a node of the tree static class node{ int data; node right, left; }; // To create a new node static 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 order static void inorder( node root) { if (root == null) return; inorder(root.left); System.out.print(root.data); inorder(root.right); } // Function to return the size of the // sub-tree rooted at the current node static int size( node root) { int a = 0, b = 0; // If root is null or the valid sub-tree // has already been found if (root == null || hasValidSubTree) return 0; // Size of the right sub-tree a = size(root.right); // 1 is added for the parent a = a + 1; // Size of the left sub-tree b = size(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 (a % 2 == 0 && root.data == a / 2) hasValidSubTree = true; return a; } // Function to update and return the sum // of all the tree nodes rooted at // the passed node static int sum_tree( node root) { if (root == null) return 0; 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 code public 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(1); root.left.right.right.left.left = newnode(1); sum_tree(root); size(root); if (hasValidSubTree) System.out.print( "Yes"); else System.out.print( "No"); } }// This code is contributed by Arnab Kundu |
Python3
# Python3 implementation of the approach class node: def __init__(self, key): self.data = key self.left = None self.right = None# Function to perform inorder traversal on # the tree and print the nodes in that order def inorder(root): if root == None: return inorder(root.left) print(root.data) inorder(root.right) # Function to return the size of the # sub-tree rooted at the current node def size(root): a, b = 0, 0 global hasValidSubTree # If root is null or the valid # sub-tree has already been found if root == None or hasValidSubTree: return 0 # Size of the right sub-tree a = size(root.right) # 1 is added for the parent a = a + 1 # Size of the left sub-tree b = size(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 a % 2 == 0 and root.data == a // 2: hasValidSubTree = True return a # Function to update and return the sum # of all the tree nodes rooted at # the passed node def sum_tree(root): if root == None: return 0 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 code if __name__ == "__main__": # To store whether the tree contains a # sub-tree with equal number of 0's and 1's hasValidSubTree = False root = node(1) root.right = node(0) root.right.right = node(1) root.right.right.right = node(1) root.left = node(0) root.left.left = node(1) root.left.left.left = node(1) root.left.right = node(0) root.left.right.left = node(1) root.left.right.left.left = node(1) root.left.right.right = node(0) root.left.right.right.left = node(1) root.left.right.right.left.left = node(1) sum_tree(root) size(root) if hasValidSubTree: print("Yes") else: print("No") # This code is contributed by Rituraj Jain |
C#
// C# implementation of the approach using System;class GFG{// To store whether the tree contains a sub-tree // with equal number of 0's and 1's static bool hasValidSubTree = false; // Represents a node of the tree public class node{ public int data; public node right, left; }; // To create a new node static 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 order static void inorder( node root) { if (root == null) return; inorder(root.left); Console.Write(root.data); inorder(root.right); } // Function to return the size of the // sub-tree rooted at the current node static int size( node root) { int a = 0, b = 0; // If root is null or the valid sub-tree // has already been found if (root == null || hasValidSubTree) return 0; // Size of the right sub-tree a = size(root.right); // 1 is added for the parent a = a + 1; // Size of the left sub-tree b = size(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 (a % 2 == 0 && root.data == a / 2) hasValidSubTree = true; return a; } // Function to update and return the sum // of all the tree nodes rooted at // the passed node static int sum_tree( node root) { if (root == null) return 0; 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 code public 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(1); root.left.right.right.left.left = newnode(1); sum_tree(root); size(root); if (hasValidSubTree) Console.Write( "Yes"); else Console.Write( "No"); } }// This code contributed by Rajput-Ji |
Javascript
<script> // JavaScript implementation of the approach // To store whether the tree contains a sub-tree // with equal number of 0's and 1's let hasValidSubTree = false; // Binary tree node class node { constructor(key) { this.left = null; this.right = null; this.data = key; } } // To create a new node function newnode(key) { let temp = new node(key); 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); inorder(root.right); } // Function to return the size of the // sub-tree rooted at the current node function size(root) { let a = 0, b = 0; // If root is null or the valid sub-tree // has already been found if (root == null || hasValidSubTree) return 0; // Size of the right sub-tree a = size(root.right); // 1 is added for the parent a = a + 1; // Size of the left sub-tree b = size(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 (a % 2 == 0 && root.data == parseInt(a / 2, 10)) hasValidSubTree = true; 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) return 0; let 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; } let 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(1); root.left.right.right.left.left = newnode(1); sum_tree(root); size(root); if (hasValidSubTree) document.write( "Yes"); else document.write( "No"); </script> |
Output:
No
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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
