Construct Binary Tree from Preorder and Inorder Traversal

[kokocan12]

Problem

When preorder, and inorder values are given, where each element is node's value, contruct binary tree.
Each element in the preorder and inorder is unique.

Approach

Preorder is traversal that move head first then move to left, right.
On the other hand, Inorder is traversal that move left first then move to head, right.

We can get the head element of the tree by picking first item of preorder.
Then, we can divide inorder into left side and right side, because we know what head value is.
Finally, we can also divide preorder, because we know the length of the left-side and the length of the right-side.

preorder = [HEAD, [LEFTSIDE], [RIGHTSIDE]]
inorder = [[LEFTSIDE], HEAD, [RIGHTSIDE]]

The code is below.

function build(preorder, inorder) {
    {
        if(preorder.length === 0) return null;
    
        const head = preorder[0];
        const root = new TreeNode(head);
    
        const headIndex = inorder.indexOf(head);

        const inorderLeft = inorder.slice(0, headIndex);
        const inorderRight = inorder.slice(headIndex+1, inorder.length);
        
    
        const preorderLeft = preorder.slice(1, 1+inorderLeft.length);
        const preorderRight = preorder.slice(1+inorderLeft.length, inorder.length);
        
        
        root.left = build(preorderLeft, inorderLeft);
        root.right = build(preorderRight, inorderRight);
        
        return root;
    }
    
}