Construct Binary Tree from Preorder and Postorder Traversal

medium binary tree divide and conquer recursion

Problem

Given two integer arrays preorder and postorder where they are traversals of a binary tree of distinct values, reconstruct and return any binary tree consistent with both. In preorder a node comes before its subtrees; in postorder a node comes after its subtrees.

Inputpreorder = [1, 2, 4, 5, 3, 6, 7], postorder = [4, 5, 2, 6, 7, 3, 1]

Output[1, 2, 3, 4, 5, 6, 7]

Root 1 has children 2 and 3; 2 has leaves 4, 5; 3 has leaves 6, 7. The level-order array describes this tree.

preorder (comma-separated)

postorder (comma-separated)

def constructFromPrePost(preorder, postorder):
    pos = {v: i for i, v in enumerate(postorder)}

    def build(pre_l, pre_r, post_l):
        if pre_l > pre_r:
            return None
        root = TreeNode(preorder[pre_l])
        if pre_l == pre_r:
            return root
        left_val = preorder[pre_l + 1]
        size = pos[left_val] - post_l + 1
        root.left = build(pre_l + 1, pre_l + size, post_l)
        root.right = build(pre_l + size + 1, pre_r, post_l + size)
        return root

    return build(0, len(preorder) - 1, 0)

function constructFromPrePost(preorder, postorder) {
  const pos = new Map();
  postorder.forEach((v, i) => pos.set(v, i));

  function build(preL, preR, postL) {
    if (preL > preR) return null;
    const root = { val: preorder[preL], left: null, right: null };
    if (preL === preR) return root;
    const leftVal = preorder[preL + 1];
    const size = pos.get(leftVal) - postL + 1;
    root.left = build(preL + 1, preL + size, postL);
    root.right = build(preL + size + 1, preR, postL + size);
    return root;
  }

  return build(0, preorder.length - 1, 0);
}

class Solution {
    int[] pre, post;
    Map<Integer, Integer> pos = new HashMap<>();

    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        pre = preorder; post = postorder;
        for (int i = 0; i < post.length; i++) pos.put(post[i], i);
        return build(0, pre.length - 1, 0);
    }

    TreeNode build(int preL, int preR, int postL) {
        if (preL > preR) return null;
        TreeNode root = new TreeNode(pre[preL]);
        if (preL == preR) return root;
        int size = pos.get(pre[preL + 1]) - postL + 1;
        root.left = build(preL + 1, preL + size, postL);
        root.right = build(preL + size + 1, preR, postL + size);
        return root;
    }
}

class Solution {
    vector<int> pre, post;
    unordered_map<int, int> pos;

    TreeNode* build(int preL, int preR, int postL) {
        if (preL > preR) return nullptr;
        TreeNode* root = new TreeNode(pre[preL]);
        if (preL == preR) return root;
        int size = pos[pre[preL + 1]] - postL + 1;
        root->left = build(preL + 1, preL + size, postL);
        root->right = build(preL + size + 1, preR, postL + size);
        return root;
    }
public:
    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
        pre = preorder; post = postorder;
        for (int i = 0; i < (int)post.size(); i++) pos[post[i]] = i;
        return build(0, pre.size() - 1, 0);
    }
};

Explanation

We rebuild a binary tree from its preorder and postorder lists. With only these two orders the answer is not always unique, but we can always produce one valid tree. The first preorder value is the root; the trick is figuring out how big the left subtree is.

The value right after the root in preorder, preorder[preL + 1], must be the left child. In postorder a subtree's root comes last, so we look up that left child's position with the map pos. The distance from postL to that index tells us the left subtree's size.

Knowing the size, we slice both arrays: the next size preorder values form the left subtree, the rest form the right. We recurse with the matching index ranges, using pos for instant lookups so the whole build stays linear.

Example: preorder = [1, 2, 4, 5, 3, 6, 7], postorder = [4, 5, 2, 6, 7, 3, 1]. Root 1; left child is 2, which sits at postorder index 2, so the left subtree has size 3 (values 2, 4, 5). The remaining 3, 6, 7 form the right subtree.

Because each node is created once and the size is found with an O(1) map lookup, the tree is reconstructed in a single linear pass.

Time: O(n) Space: O(n)