Find largest subtree having identical left and right subtrees | C ++ 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 ; Helper function that allocates a new node with the given data and NULL left and right pointers . ; 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 . ; string to store structure of left and right subtrees ; traverse left subtree and finds its size ; traverse right subtree and finds its size ; 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 ) ; append left subtree data ; append current node data ; append right subtree data ; function to find the largest subtree having identical left and right subtree ; Driver program to test above functions ; Let us construct the following Tree 50 / \ 10 60 / \ / \ 5 20 70 70 / \ / \ 65 80 65 80
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; Node * left , * right ; } ; Node * newNode ( int data ) { Node * node = new Node ; node -> data = data ; node -> left = node -> right = NULL ; return ( node ) ; } int largestSubtreeUtil ( Node * root , string & str , int & maxSize , Node * & maxNode ) { if ( root == NULL ) return 0 ; string left = " " , right = " " ; int ls = largestSubtreeUtil ( root -> left , left , maxSize , maxNode ) ; int rs = largestSubtreeUtil ( root -> right , right , maxSize , maxNode ) ; int size = ls + rs + 1 ; if ( left . compare ( right ) == 0 ) { if ( size > maxSize ) { maxSize = size ; maxNode = root ; } } str . append ( " ▁ " ) . append ( left ) . append ( " ▁ " ) ; str . append ( " ▁ " ) . append ( to_string ( root -> data ) ) . append ( " ▁ " ) ; str . append ( " ▁ " ) . append ( right ) . append ( " ▁ " ) ; return size ; } int largestSubtree ( Node * node , Node * & maxNode ) { int maxSize = 0 ; string str = " " ; largestSubtreeUtil ( node , str , maxSize , maxNode ) ; return maxSize ; } int main ( ) { 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 << " and its size is " << maxSize ; return 0 ; }