Find all possible binary trees with given Inorder Traversal | Node Structure ; Utility to create a new node ; A utility function to do preorder traversal of BST ; Function for constructing all possible trees with given inorder traversal stored in an array from arr [ start ] to arr [ end ] . This function returns a vector of trees . ; List to store all possible trees ; if start > end then subtree will be empty so returning NULL in the list ; Iterating through all values from start to end for constructing left and right subtree recursively ; Constructing left subtree ; Constructing right subtree ; Looping through all left and right subtrees and connecting to ith root below ; Making arr [ i ] as root ; Connecting left subtree ; Connecting right subtree ; Adding this tree to list ; Driver program to test above function
class Node : NEW_LINE INDENT def __init__ ( self , item ) : NEW_LINE INDENT self . key = item NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def preorder ( root ) : NEW_LINE INDENT if root is not None : NEW_LINE INDENT print root . key , NEW_LINE preorder ( root . left ) NEW_LINE preorder ( root . right ) NEW_LINE DEDENT DEDENT def getTrees ( arr , start , end ) : NEW_LINE INDENT trees = [ ] NEW_LINE if start > end : NEW_LINE INDENT trees . append ( None ) NEW_LINE return trees NEW_LINE DEDENT for i in range ( start , end + 1 ) : NEW_LINE INDENT ltrees = getTrees ( arr , start , i - 1 ) NEW_LINE rtrees = getTrees ( arr , i + 1 , end ) NEW_LINE for j in ltrees : NEW_LINE INDENT for k in rtrees : NEW_LINE INDENT node = Node ( arr [ i ] ) NEW_LINE node . left = j NEW_LINE node . right = k NEW_LINE trees . append ( node ) NEW_LINE DEDENT DEDENT DEDENT return trees NEW_LINE DEDENT inp = [ 4 , 5 , 7 ] NEW_LINE n = len ( inp ) NEW_LINE trees = getTrees ( inp , 0 , n - 1 ) NEW_LINE print " Preorder ▁ traversals ▁ of ▁ different ▁ possible\ STRNEWLINE ▁ Binary ▁ Trees ▁ are ▁ " NEW_LINE for i in trees : NEW_LINE INDENT preorder ( i ) ; NEW_LINE print " " NEW_LINE DEDENT