Construct a Binary Tree from Postorder and Inorder | A binary tree node has data , pointer to left child and a pointer to right child ; Recursive function to construct binary of size n from Inorder traversal in [ ] and Postrder traversal post [ ] . Initial values of inStrt and inEnd should be 0 and n - 1. The function doesn 't do any error  checking for cases where inorder and postorder  do not form a tree  ; Base case ; Pick current node from Postrder traversal using postIndex and decrement postIndex ; If this node has no children then return ; Else find the index of this node in Inorder traversal ; Using index in Inorder traversal , construct left and right subtress ; Function to find index of value in arr [ start ... end ] The function assumes that value is postsent in in [ ] ; This funtcion is here just to test ; Driver Code
class Node { constructor ( data ) { this . data = data ; this . left = this . right = null ; } } function buildUtil ( In , post , inStrt , inEnd , postStrt , postEnd ) { if ( inStrt > inEnd ) return null ; let node = new Node ( post [ postEnd ] ) ; if ( inStrt == inEnd ) return node ; let iIndex = search ( In , inStrt , inEnd , node . data ) ; node . left = buildUtil ( In , post , inStrt , iIndex - 1 , postStrt , postStrt - inStrt + iIndex - 1 ) ; node . right = buildUtil ( In , post , iIndex + 1 , inEnd , postEnd - inEnd + iIndex , postEnd - 1 ) ; return node ; } function search ( arr , strt , end , value ) { let i ; for ( i = strt ; i <= end ; i ++ ) { if ( arr [ i ] == value ) break ; } return i ; } function preOrder ( node ) { if ( node == null ) return ; document . write ( node . data + " " ) ; preOrder ( node . left ) ; preOrder ( node . right ) ; } let In = [ 4 , 8 , 2 , 5 , 1 , 6 , 3 , 7 ] ; let post = [ 8 , 4 , 5 , 2 , 6 , 7 , 3 , 1 ] ; let n = In . length ; let root = buildUtil ( In , post , 0 , n - 1 , 0 , n - 1 ) ; document . write ( " " ) ; preOrder ( root ) ;