Find largest subtree having identical left and right subtrees | Helper class that allocates a new node with the given data and None 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 Code ; Let us construct the following Tree 50 / \ 10 60 / \ / \ 5 20 70 70 / \ / \ 65 80 65 80
class newNode : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = self . right = None NEW_LINE DEDENT DEDENT def largestSubtreeUtil ( root , Str , maxSize , maxNode ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT left = [ " " ] NEW_LINE right = [ " " ] NEW_LINE ls = largestSubtreeUtil ( root . left , left , maxSize , maxNode ) NEW_LINE rs = largestSubtreeUtil ( root . right , right , maxSize , maxNode ) NEW_LINE size = ls + rs + 1 NEW_LINE if ( left [ 0 ] == right [ 0 ] ) : NEW_LINE INDENT if ( size > maxSize [ 0 ] ) : NEW_LINE INDENT maxSize [ 0 ] = size NEW_LINE maxNode [ 0 ] = root NEW_LINE DEDENT DEDENT Str [ 0 ] = Str [ 0 ] + " | " + left [ 0 ] + " | " NEW_LINE Str [ 0 ] = Str [ 0 ] + " | " + str ( root . data ) + " | " NEW_LINE Str [ 0 ] = Str [ 0 ] + " | " + right [ 0 ] + " | " NEW_LINE return size NEW_LINE DEDENT def largestSubtree ( node , maxNode ) : NEW_LINE INDENT maxSize = [ 0 ] NEW_LINE Str = [ " " ] NEW_LINE largestSubtreeUtil ( node , Str , maxSize , maxNode ) NEW_LINE return maxSize NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = newNode ( 50 ) NEW_LINE root . left = newNode ( 10 ) NEW_LINE root . right = newNode ( 60 ) NEW_LINE root . left . left = newNode ( 5 ) NEW_LINE root . left . right = newNode ( 20 ) NEW_LINE root . right . left = newNode ( 70 ) NEW_LINE root . right . left . left = newNode ( 65 ) NEW_LINE root . right . left . right = newNode ( 80 ) NEW_LINE root . right . right = newNode ( 70 ) NEW_LINE root . right . right . left = newNode ( 65 ) NEW_LINE root . right . right . right = newNode ( 80 ) NEW_LINE maxNode = [ None ] NEW_LINE maxSize = largestSubtree ( root , maxNode ) NEW_LINE print ( " Largest ▁ Subtree ▁ is ▁ rooted ▁ at ▁ node ▁ " , maxNode [ 0 ] . data ) NEW_LINE print ( " and ▁ its ▁ size ▁ is ▁ " , maxSize ) NEW_LINE DEDENT