Find all possible binary trees with given Inorder Traversal | Java program to find binary tree with given inorder traversal ; Class containing left and right child of current node and key value ; Class to print Level Order Traversal ; 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 ; Now looping through all left and right subtrees and connecting them 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 functions
import java . util . Vector ; class Node { int data ; Node left , right ; public Node ( int item ) { data = item ; left = null ; right = null ; } } class BinaryTree { Node root ; void preOrder ( Node node ) { if ( node != null ) { System . out . print ( node . data + " ▁ " ) ; preOrder ( node . left ) ; preOrder ( node . right ) ; } } Vector < Node > getTrees ( int arr [ ] , int start , int end ) { Vector < Node > trees = new Vector < Node > ( ) ; if ( start > end ) { trees . add ( null ) ; return trees ; } for ( int i = start ; i <= end ; i ++ ) { Vector < Node > ltrees = getTrees ( arr , start , i - 1 ) ; Vector < Node > rtrees = getTrees ( arr , i + 1 , end ) ; for ( int j = 0 ; j < ltrees . size ( ) ; j ++ ) { for ( int k = 0 ; k < rtrees . size ( ) ; k ++ ) { Node node = new Node ( arr [ i ] ) ; node . left = ltrees . get ( j ) ; node . right = rtrees . get ( k ) ; trees . add ( node ) ; } } } return trees ; } public static void main ( String args [ ] ) { int in [ ] = { 4 , 5 , 7 } ; int n = in . length ; BinaryTree tree = new BinaryTree ( ) ; Vector < Node > trees = tree . getTrees ( in , 0 , n - 1 ) ; System . out . println ( " Preorder ▁ traversal ▁ of ▁ different ▁ " + " ▁ binary ▁ trees ▁ are : " ) ; for ( int i = 0 ; i < trees . size ( ) ; i ++ ) { tree . preOrder ( trees . get ( i ) ) ; System . out . println ( " " ) ; } } }