Construct Binary Tree from Inorder and Preorder Traversal

Home | Coding Interviews | Simple Data Structures | Construct Binary Tree from Inorder and Preorder Traversal

Simple Data Structures Medium Video Code Solution Javascript

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    let hash = {};
    inorder.forEach((e, i)=>{hash[e] = i});
    
    let recur = function(start, end) {
        if (start > end) return null;
        let root = new TreeNode(preorder.shift());
        root.left = recur(start, hash[root.val] - 1);
        root.right = recur(hash[root.val] + 1, end);
        return root;
    }
    
    return recur(0, inorder.length - 1);    
};

Posted by Jamie Meyer 20 days ago