Construct Binary Tree from Preorder and Postorder

Master this topic with zero to advance depth.

Construct Binary Tree from Preorder and Postorder

Rebuild tree.

Hard

Approach 1

Level I: Recursive with Subarray Search

Intuition

In both preorder and postorder, the first element (or last in postorder) is the root. The element after the root in preorder (preorder[1]) is the root of the left subtree. We find this element in the postorder array; all elements before it in postorder belong to the left subtree.

Thought Process

root = preorder[0].
Left Root = preorder[1].
Find index of preorder[1] in postorder (linear search).
All elements until that index in postorder are in the left subtree.

⏱ O(N^2)💾 O(N)

Detailed Dry Run

Preorder	Postorder	Left Root	Post Index	Left Size
[1,2,4,5,3,6,7]	[4,5,2,6,7,3,1]	2	2	3

java

import java.util.*;

public class Main {
    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        return build(pre, 0, pre.length - 1, post, 0, post.length - 1);
    }

    private TreeNode build(int[] pre, int preS, int preE, int[] post, int postS, int postE) {
        if (preS > preE) return null;
        TreeNode root = new TreeNode(pre[preS]);
        if (preS == preE) return root;

        int leftVal = pre[preS + 1];
        int idx = postS;
        while (post[idx] != leftVal) idx++;
        int leftSize = idx - postS + 1;

        root.left = build(pre, preS + 1, preS + leftSize, post, postS, idx);
        root.right = build(pre, preS + leftSize + 1, preE, post, idx + 1, postE - 1);
        return root;
    }

    public static void main(String[] args) {
        int[] pre = {1, 2, 4, 5, 3, 6, 7}, post = {4, 5, 2, 6, 7, 3, 1};
        TreeNode root = new Main().constructFromPrePost(pre, post);
        System.out.println(root.val); // 1
    }
}

Approach 2

Level III: Optimal (Index-based Recursion)

Intuition

Thought Process

Instead of full array slicing or repeated index searching, we maintain global pointers/indices and use a Hash Map for $O(1)$ lookups of the left child's position in the postorder array.

Diagram

Pre: [1, 2, 4, 5, 3, 6, 7]
Idx:  0, 1, 2, 3, 4, 5, 6

If we are at 1, next is 2.
Find 2 in Post: Index 2.
Left Subtree count = 2 - 0 + 1 = 3.

⏱ O(N)💾 O(N)

Detailed Dry Run

Pre Index	Node Val	Left Val	Post Map Idx	Action
0	1	2	2	Build 1, proceed to Left
1	2	4	0	Build 2, proceed to Left
2	4	-	-	Leaf 4, return

java

public class Main {
    int preI = 0, postI = 0;
    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        TreeNode root = new TreeNode(pre[preI++]);
        if (root.val != post[postI]) root.left = constructFromPrePost(pre, post);
        if (root.val != post[postI]) root.right = constructFromPrePost(pre, post);
        postI++;
        return root;
    }
}

⚠️ Common Pitfalls & Tips

Note that this construction (Pre+Post) does not uniquely define a tree if any node has only one child. The standard implementation treats the single child as the left child.

← Previous QuestionVertical Order Traversal

Next Question →House Robber III

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.