Given a binary tree, find the largest subtree having identical left and right subtree. Expected complexity is O(n).
For example,
Input: 50 / \ 10 60 / \ / \ 5 20 70 70 / \ / \ 65 80 65 80 Output: Largest subtree is rooted at node 60
A simple solution is to consider every node, recursively check if left and right subtrees are identical using the approach discussed here. Keep track of maximum size such node.
We can save recursive calls. The idea is to do a postorder traversal of given binary tree and for each node, we store structure of its left and right subtrees. In order to store the structure of left and right subtree, we use a string. We separate left and right subtree nodes from current node in the string by using a delimiter. For every encountered node, we update largest subtree found so far if its left and right subtree structure are similar.
Below is implementation of above idea:
C++
// C++ program to find the largest subtree // having identical left and right subtree #include <bits/stdc++.h> using namespace std; /* A binary tree node has data, pointer to left child and a pointer to right child */ struct Node { int data; Node* left, * right; }; /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ Node* newNode( int data) { Node* node = new Node; node->data = data; node->left = node->right = NULL; return (node); } // Sets maxSize to size of largest subtree with // identical left and right. maxSize is set with // size of the maximum sized subtree. It returns // size of subtree rooted with current node. This // size is used to keep track of maximum size. int largestSubtreeUtil(Node* root, string& str, int & maxSize, Node*& maxNode) { if (root == NULL) return 0; // string to store structure of left and // right subtrees string left = "" , right = "" ; // traverse left subtree and finds its size int ls = largestSubtreeUtil(root->left, left, maxSize, maxNode); // traverse right subtree and finds its size int rs = largestSubtreeUtil(root->right, right, maxSize, maxNode); // if left and right subtrees are similar // update maximum subtree if needed (Note that // left subtree may have a bigger value than // right and vice versa) int size = ls + rs + 1; if (left.compare(right) == 0) { if (size > maxSize) { maxSize = size; maxNode = root; } } // append left subtree data str.append( "|" ).append(left).append( "|" ); // append current node data str.append( "|" ).append(to_string(root->data)).append( "|" ); // append right subtree data str.append( "|" ).append(right).append( "|" ); return size; } // function to find the largest subtree // having identical left and right subtree int largestSubtree(Node* node, Node*& maxNode) { int maxSize = 0; string str = "" ; largestSubtreeUtil(node, str, maxSize, maxNode); return maxSize; } /* Driver program to test above functions*/ int main() { /* Let us construct the following Tree 50 / \ 10 60 / \ / \ 5 20 70 70 / \ / \ 65 80 65 80 */ Node* root = newNode(50); root->left = newNode(10); root->right = newNode(60); root->left->left = newNode(5); root->left->right = newNode(20); root->right->left = newNode(70); root->right->left->left = newNode(65); root->right->left->right = newNode(80); root->right->right = newNode(70); root->right->right->left = newNode(65); root->right->right->right = newNode(80); Node *maxNode = NULL; int maxSize = largestSubtree(root, maxNode); cout << "Largest Subtree is rooted at node " << maxNode->data << "\nand its size is " << maxSize; return 0; } |
Java
// Java program to find the largest subtree // having identical left and right subtree class GFG { /* A binary tree node has data, pointer to left child and a pointer to right child */ static class Node { int data; Node left, right; }; /* Helper function that allocates a new node with the given data and null left and right pointers. */ static Node newNode( int data) { Node node = new Node(); node.data = data; node.left = node.right = null ; return (node); } static class string { String str; } static int maxSize; static Node maxNode; static class pair { int first; String second; pair( int a, String b) { first = a; second = b; } } // Sets maxSize to size of largest subtree with // identical left and right. maxSize is set with // size of the maximum sized subtree. It returns // size of subtree rooted with current node. This // size is used to keep track of maximum size. static pair largestSubtreeUtil(Node root, String str) { if (root == null ) return new pair( 0 , str); // string to store structure of left and // right subtrees String left = "" , right= "" ; // traverse left subtree and finds its size pair ls1 = largestSubtreeUtil(root.left, left); left = ls1.second; int ls = ls1.first; // traverse right subtree and finds its size pair rs1 = largestSubtreeUtil(root.right, right); right = rs1.second; int rs = rs1.first; // if left and right subtrees are similar // update maximum subtree if needed (Note that // left subtree may have a bigger value than // right and vice versa) int size = ls + rs + 1 ; if (left.equals(right)) { if (size > maxSize) { maxSize = size; maxNode = root; } } // append left subtree data str += "|" +left+ "|" ; // append current node data str += "|" +root.data+ "|" ; // append right subtree data str += "|" +right+ "|" ; return new pair(size, str); } // function to find the largest subtree // having identical left and right subtree static int largestSubtree(Node node) { maxSize = 0 ; largestSubtreeUtil(node, "" ); return maxSize; } /* Driver program to test above functions*/ public static void main(String args[]) { /* Let us construct the following Tree 50 / \ 10 60 / \ / \ 5 20 70 70 / \ / \ 65 80 65 80 */ Node root = newNode( 50 ); root.left = newNode( 10 ); root.right = newNode( 60 ); root.left.left = newNode( 5 ); root.left.right = newNode( 20 ); root.right.left = newNode( 70 ); root.right.left.left = newNode( 65 ); root.right.left.right = newNode( 80 ); root.right.right = newNode( 70 ); root.right.right.left = newNode( 65 ); root.right.right.right = newNode( 80 ); maxNode = null ; maxSize = largestSubtree(root); System.out.println( "Largest Subtree is rooted at node " + maxNode.data + "\nand its size is " + maxSize); } } // This code is contributed by Arnab Kundu |
Python3
# Python3 program to find the largest subtree # having identical left and right subtree # Helper class that allocates a new node # with the given data and None left and # right pointers. class newNode: def __init__( self , data): self .data = data self .left = self .right = None # Sets maxSize to size of largest subtree with # identical left and right. maxSize is set with # size of the maximum sized subtree. It returns # size of subtree rooted with current node. This # size is used to keep track of maximum size. def largestSubtreeUtil(root, Str , maxSize, maxNode): if (root = = None ): return 0 # string to store structure of left # and right subtrees left = [""] right = [""] # traverse left subtree and finds its size ls = largestSubtreeUtil(root.left, left, maxSize, maxNode) # traverse right subtree and finds its size rs = largestSubtreeUtil(root.right, right, maxSize, maxNode) # if left and right subtrees are similar # update maximum subtree if needed (Note # that left subtree may have a bigger # value than right and vice versa) size = ls + rs + 1 if (left[ 0 ] = = right[ 0 ]): if (size > maxSize[ 0 ]): maxSize[ 0 ] = size maxNode[ 0 ] = root # append left subtree data Str [ 0 ] = Str [ 0 ] + "|" + left[ 0 ] + "|" # append current node data Str [ 0 ] = Str [ 0 ] + "|" + str (root.data) + "|" # append right subtree data Str [ 0 ] = Str [ 0 ] + "|" + right[ 0 ] + "|" return size # function to find the largest subtree # having identical left and right subtree def largestSubtree(node, maxNode): maxSize = [ 0 ] Str = [""] largestSubtreeUtil(node, Str , maxSize, maxNode) return maxSize # Driver Code if __name__ = = '__main__' : # Let us construct the following Tree # 50 # / \ # 10 60 # / \ / \ # 5 20 70 70 # / \ / \ # 65 80 65 80 root = newNode( 50 ) root.left = newNode( 10 ) root.right = newNode( 60 ) root.left.left = newNode( 5 ) root.left.right = newNode( 20 ) root.right.left = newNode( 70 ) root.right.left.left = newNode( 65 ) root.right.left.right = newNode( 80 ) root.right.right = newNode( 70 ) root.right.right.left = newNode( 65 ) root.right.right.right = newNode( 80 ) maxNode = [ None ] maxSize = largestSubtree(root, maxNode) print ( "Largest Subtree is rooted at node " , maxNode[ 0 ].data) print ( "and its size is " , maxSize) # This code is contributed by PranchalK |
C#
// C# program to find the largest subtree // having identical left and right subtree using System; class GFG{ // A binary tree node has data, pointer to // left child and a pointer to right child public class Node { public int data; public Node left, right; }; // Helper function that allocates a new node // with the given data and null left and // right pointers. static Node newNode( int data) { Node node = new Node(); node.data = data; node.left = node.right = null ; return (node); } static int maxSize; static Node maxNode; public class pair { public int first; public string second; public pair( int a, string b) { first = a; second = b; } } // Sets maxSize to size of largest subtree with // identical left and right. maxSize is set with // size of the maximum sized subtree. It returns // size of subtree rooted with current node. This // size is used to keep track of maximum size. static pair largestSubtreeUtil(Node root, string str) { if (root == null ) return new pair(0, str); // String to store structure of left and // right subtrees string left = "" , right = "" ; // Traverse left subtree and finds its size pair ls1 = largestSubtreeUtil(root.left, left); left = ls1.second; int ls = ls1.first; // Traverse right subtree and finds its size pair rs1 = largestSubtreeUtil(root.right, right); right = rs1.second; int rs = rs1.first; // If left and right subtrees are similar // update maximum subtree if needed (Note // that left subtree may have a bigger // value than right and vice versa) int size = ls + rs + 1; if (left.Equals(right)) { if (size > maxSize) { maxSize = size; maxNode = root; } } // Append left subtree data str += "|" + left + "|" ; // Append current node data str += "|" + root.data + "|" ; // Append right subtree data str += "|" + right + "|" ; return new pair(size, str); } // Function to find the largest subtree // having identical left and right subtree static int largestSubtree(Node node) { maxSize = 0; largestSubtreeUtil(node, "" ); return maxSize; } // Driver code public static void Main( string []args) { /* Let us construct the following Tree 50 / \ 10 60 / \ / \ 5 20 70 70 / \ / \ 65 80 65 80 */ Node root = newNode(50); root.left = newNode(10); root.right = newNode(60); root.left.left = newNode(5); root.left.right = newNode(20); root.right.left = newNode(70); root.right.left.left = newNode(65); root.right.left.right = newNode(80); root.right.right = newNode(70); root.right.right.left = newNode(65); root.right.right.right = newNode(80); maxNode = null ; maxSize = largestSubtree(root); Console.Write( "Largest Subtree is rooted at node " + maxNode.data + "\nand its size is " + maxSize); } } // This code is contributed by pratham76 |
Javascript
<script> // Javascript program to find the largest subtree // having identical left and right subtree // A binary tree node has data, pointer to // left child and a pointer to right child class Node { constructor() { this .data = 0; this .left = null ; this .right = null ; } }; // Helper function that allocates a new node // with the given data and null left and // right pointers. function newNode(data) { var node = new Node(); node.data = data; node.left = node.right = null ; return (node); } var maxSize = 0; var maxNode = null ; class pair { constructor(a, b) { this .first = a; this .second = b; } } // Sets maxSize to size of largest subtree with // identical left and right. maxSize is set with // size of the maximum sized subtree. It returns // size of subtree rooted with current node. This // size is used to keep track of maximum size. function largestSubtreeUtil(root, str) { if (root == null ) return new pair(0, str); // String to store structure of left and // right subtrees var left = "" , right = "" ; // Traverse left subtree and finds its size var ls1 = largestSubtreeUtil(root.left, left); left = ls1.second; var ls = ls1.first; // Traverse right subtree and finds its size var rs1 = largestSubtreeUtil(root.right, right); right = rs1.second; var rs = rs1.first; // If left and right subtrees are similar // update maximum subtree if needed (Note // that left subtree may have a bigger // value than right and vice versa) var size = ls + rs + 1; if (left == right) { if (size > maxSize) { maxSize = size; maxNode = root; } } // Append left subtree data str += "|" + left + "|" ; // Append current node data str += "|" + root.data + "|" ; // Append right subtree data str += "|" + right + "|" ; return new pair(size, str); } // Function to find the largest subtree // having identical left and right subtree function largestSubtree(node) { maxSize = 0; largestSubtreeUtil(node, "" ); return maxSize; } // Driver code /* Let us construct the following Tree 50 / \ 10 60 / \ / \ 5 20 70 70 / \ / \ 65 80 65 80 */ var root = newNode(50); root.left = newNode(10); root.right = newNode(60); root.left.left = newNode(5); root.left.right = newNode(20); root.right.left = newNode(70); root.right.left.left = newNode(65); root.right.left.right = newNode(80); root.right.right = newNode(70); root.right.right.left = newNode(65); root.right.right.right = newNode(80); maxNode = null ; maxSize = largestSubtree(root); document.write( "Largest Subtree is rooted at node " + maxNode.data + "<br>and its size is " + maxSize); // This code is contributed by itsok. </script> |
Largest Subtree is rooted at node 60 and its size is 7
The worst case time complexity still remains O(n2) as we need O(n) time to compare two strings.
Space Complexity: O(n)
Further Optimization:
We can optimized the space used in above program by using Succinct Encoding of Binary Tree.
This article is contributed by Aditya Goel. If you like neveropen and would like to contribute, you can also write an article and mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!