Construct a special tree from given preorder traversal | A Binary Tree node ; A recursive function to create a Binary Tree from given pre [ ] preLN [ ] arrays . The function returns root of tree . index_ptr is used to update index values in recursive calls . index must be initially passed as 0 ; store the current value of index in pre [ ] ; Base Case : All nodes are constructed ; Allocate memory for this node and increment index for subsequent recursive calls ; If this is an internal node , construct left and right subtrees and link the subtrees ; A wrapper over constructTreeUtil ( ) ; Initialize index as 0. Value of index is used in recursion to maintain the current index in pre [ ] and preLN [ ] arrays . ; This function is used only for testing ; first recur on left child ; then print the data of node ; now recur on right child ; driver function to test the above functions
class Node { int data ; Node left , right ; Node ( int item ) { data = item ; left = right = null ; } } class Index { int index = 0 ; } class BinaryTree { Node root ; Index myindex = new Index ( ) ; Node constructTreeUtil ( int pre [ ] , char preLN [ ] , Index index_ptr , int n , Node temp ) { int index = index_ptr . index ; if ( index == n ) return null ; temp = new Node ( pre [ index ] ) ; ( index_ptr . index ) ++ ; if ( preLN [ index ] == ' N ' ) { temp . left = constructTreeUtil ( pre , preLN , index_ptr , n , temp . left ) ; temp . right = constructTreeUtil ( pre , preLN , index_ptr , n , temp . right ) ; } return temp ; } Node constructTree ( int pre [ ] , char preLN [ ] , int n , Node node ) { int index = 0 ; return constructTreeUtil ( pre , preLN , myindex , n , node ) ; } void printInorder ( Node node ) { if ( node == null ) return ; printInorder ( node . left ) ; System . out . print ( node . data + " ▁ " ) ; printInorder ( node . right ) ; } public static void main ( String args [ ] ) { BinaryTree tree = new BinaryTree ( ) ; int pre [ ] = new int [ ] { 10 , 30 , 20 , 5 , 15 } ; char preLN [ ] = new char [ ] { ' N ' , ' N ' , ' L ' , ' L ' , ' L ' } ; int n = pre . length ; Node mynode = tree . constructTree ( pre , preLN , n , tree . root ) ; System . out . println ( " Following ▁ is ▁ Inorder ▁ Traversal ▁ of ▁ the " + " Constructed ▁ Binary ▁ Tree : ▁ " ) ; tree . printInorder ( mynode ) ; } }