Find largest subtree having identical left and right subtrees | Java 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
class GFG { static class Node { int data ; Node left , right ; } ; 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 ; } } static pair largestSubtreeUtil ( Node root , String str ) { if ( root == null ) return new pair ( 0 , str ) ; String left = " " , right = " " ; pair ls1 = largestSubtreeUtil ( root . left , left ) ; left = ls1 . second ; int ls = ls1 . first ; pair rs1 = largestSubtreeUtil ( root . right , right ) ; right = rs1 . second ; int rs = rs1 . first ; int size = ls + rs + 1 ; if ( left . equals ( right ) ) { if ( size > maxSize ) { maxSize = size ; maxNode = root ; } } str += " | " + left + " | " ; str += " | " + root . data + " | " ; str += " | " + right + " | " ; return new pair ( size , str ) ; } static int largestSubtree ( Node node ) { maxSize = 0 ; largestSubtreeUtil ( node , " " ) ; return maxSize ; } public static void main ( String args [ ] ) { 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 + " and its size is " + maxSize); } }