Leetcode•Apr 02, 2026

Construct Binary Tree from Inorder and Postorder Traversal

Hazrat Ali

Leetcode

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

 

Example 1:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

Example 2:

Input: inorder = [-1], postorder = [-1]
Output: [-1]

Solution
var buildTree = function(inorder, postorder) {
    let map = new Map();
   
    for (let i = 0; i < inorder.length; i++) {
        map.set(inorder[i], i);
    }

    let postIndex = postorder.length - 1;

    function helper(left, right) {
        if (left > right) return null;

        let rootVal = postorder[postIndex--];
        let root = new TreeNode(rootVal);

        let index = map.get(rootVal);

        root.right = helper(index + 1, right);
        root.left = helper(left, index - 1);

        return root;
    }

    return helper(0, inorder.length - 1);
};




Comments