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 code ; Let us construct the following Tree 50 / \ 10 60 / \ / \ 5 20 70 70 / \ / \ 65 80 65 80
using System ; class GFG { public class Node { public int data ; public Node left , right ; } ; 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 ; } } 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 ) ; Console . Write ( " Largest ▁ Subtree ▁ is ▁ rooted ▁ at ▁ node ▁ " + maxNode . data + " and size is " } }