DSA sheet · Trees · Construction pattern

Build Tree from Preorder & Postorder

The third construction problem, and the teacher admits it is a little harder than the two before it (preorder + inorder and inorder + postorder). This time there is no inorder list, so nothing tells us directly where the left subtree ends. The trick she teaches: the node right after the root in preorder is the left subtree's root, and its position in postorder tells us how big the left subtree is. With that size we can cut both lists into "left part" and "right part". Because we must cut two lists, we track four indexes instead of two.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Build the tree with four index pointers
• Part B · Revision page

Part 0 · Before starting

Recap of the orders we're given

A subtree is a node with everything below it. The size of a subtree is how many nodes it has. A leaf is a node with no children.

The example tree

          1
        /   \
       2     3
      / \   / \
     4   5 6   7

index:        0  1  2  3  4  5  6
preorder  = [ 1, 2, 4, 5, 3, 6, 7 ]
postorder = [ 4, 5, 2, 6, 7, 3, 1 ]

What's different from the last two problems?

Both preorder and postorder tell us who the root is (first of preorder, last of postorder). Neither of them, alone, tells us where the left subtree stops and the right subtree starts. Inorder did that job before. Now we have to work out that boundary ourselves.

   1          1
  /            \
 2              2

Part A · Build the tree with four index pointers

LeetCode 889 · Construct Binary Tree from Preorder and Postorder Traversal

1The question in simple words

You get preorder and postorder of one binary tree (not a binary search tree, just a binary tree). Rebuild it and return its root. If more than one tree fits, any of them is accepted.

input:  preorder  = [1, 2, 4, 5, 3, 6, 7]
        postorder = [4, 5, 2, 6, 7, 3, 1]

output: the root of        1
                         /   \
                        2     3
                       / \   / \
                      4   5 6   7

2What the constraints tell us

• 1 ≤ preorder.length ≤ 30 → at least one node, at most 30. Tiny, so speed is not a worry at all; even O(n²) is fine. We still write the clean O(n) version.
• Values from 1 to n, and all values are unique (in both lists). The teacher marks this as very important: it's what lets us store "value → index in postorder" in a hashmap.
• postorder.length == preorder.length → both list every node once.
• The lists are guaranteed to come from a real binary tree, so we never have to handle broken input.

3Intuition: how to think about it

Look at preorder: [1 | 2, 4, 5 | 3, 6, 7]. The root 1 comes first, then the whole left subtree, then the whole right subtree. If only we knew that the left subtree has 3 nodes, we could cut preorder right there.

Who is the left subtree's root? In preorder, the node right after the root, so 2. Now find 2 in postorder: [4, 5, 2 | 6, 7, 3 | 1]. Postorder writes the root of a subtree after all its other nodes, so 2 is the last node of the left subtree there. Everything from the start up to 2 is the left subtree: 3 nodes.

preorder  = [ 1 | 2  4  5 | 3  6  7 ]        left root = 2 (next after the root)
              ^   -------   -------
             root   left     right

postorder = [ 4  5  2 | 6  7  3 | 1 ]        2 sits at index 2 → left size = 3
              -------   -------   ^
               left      right   root

So the picture is: preorder gives the left root, postorder gives the left size, and the size cuts both lists. Then do the same for each half.

4Building the logic from the example

Step 1 · The root

The root of the window is the first value of its preorder part: preorder[pre_start]. (For the full tree it's also the last of postorder, but we read it from preorder.) The teacher first writes index 0, then notices the next call needs a different start (2 will be the root of the next call), so she uses a variable pre_start instead.

Step 2 · The left root and its index in postorder

left_root = preorder[pre_start + 1] = 2. To find where 2 sits in postorder in O(1), we fill a hashmap once at the start: pos[value] = index in postorder. pos[2] = 2.

Step 3 · The size of the left subtree

This is the usual "right − left + 1" count of how many cells lie between two indexes, using the postorder window: it starts at post_start and the left subtree ends at idx.

Step 4 · The four indexes for the left call

The teacher compares two choices. Either slice the lists and send smaller copies, or send the same full lists every time with indexes that mark the allowed part. Slicing costs extra O(n) work at every call, so she goes with indexes: pre_start, pre_end for preorder and post_start, post_end for postorder.

On screen she first said the left post end would be "size", then corrected herself to idx. In the top call they happen to be close (size 3, idx 2), but idx is the right one: the left subtree ends exactly where its root sits in postorder.

Step 5 · The four indexes for the right call

Step 6 · The base cases (there are two)

(a) Empty window. When the start passes the end, there are no nodes → return None, because the caller is waiting for a node to attach and "no node" is None.

(b) Exactly one node. When pre_start == pre_end, the window holds one node, a leaf. The teacher asks: should we still go left and right? No. Make the node and return it straight away.

Step 7 · Return the root so it gets linked

The empty-window return None covers missing children. But a real node must also be handed back: after 4 gets None and None, it returns 4 so it lands in 2.left; 2 returns itself to land in 1.left. Nodes are made going down, and joined into one tree as each call returns.

Why not just slice? (the version she rejects)

For comparison, here is the slicing idea written out. It's shorter to read, and with n ≤ 30 it would pass, but every slice and every .index() walks part of a list, so each call does O(n) extra work: O(n²) overall.

class Solution:
    def constructFromPrePost(self, preorder, postorder):
        if not preorder:                           # empty part
            return None
        root = TreeNode(preorder[0])
        if len(preorder) == 1:                     # a leaf
            return root
        idx = postorder.index(preorder[1])         # O(n) search
        size = idx + 1                             # here every slice starts at 0
        root.left = self.constructFromPrePost(preorder[1:size + 1], postorder[:size])
        root.right = self.constructFromPrePost(preorder[size + 1:], postorder[size:-1])
        return root

Note that here size = idx + 1 is correct, because each slice is a fresh list starting at index 0. In the index version the window does not start at 0, which is exactly why Step 3 subtracts post_start.

5Approach steps

1. Fill pos[postorder[i]] = i for every i.
2. Call build(0, n-1, 0, n-1) (preorder window, postorder window).
3. If pre_start > pre_end → return None.
4. Make root from preorder[pre_start].
5. If pre_start == pre_end → it's a leaf, return root.
6. left_root = preorder[pre_start + 1], idx = pos[left_root], size = idx - post_start + 1.
7. Left: preorder pre_start+1 .. pre_start+size, postorder post_start .. idx.
8. Right: preorder pre_start+size+1 .. pre_end, postorder idx+1 .. post_end-1.
9. Return root.

6Code (Python)

class Solution:
    def constructFromPrePost(self, preorder, postorder):
        self.pos = {}                                # value -> index in postorder
        for i in range(len(postorder)):
            self.pos[postorder[i]] = i
        n = len(preorder)
        return self.build(preorder, 0, n - 1, postorder, 0, n - 1)

    def build(self, preorder, pre_start, pre_end, postorder, post_start, post_end):
        if pre_start > pre_end:                      # empty window
            return None
        root = TreeNode(preorder[pre_start])
        if pre_start == pre_end:                     # one node: a leaf
            return root

        left_root = preorder[pre_start + 1]          # root of the left subtree
        idx = self.pos[left_root]                    # where it sits in postorder
        size = idx - post_start + 1                  # nodes in the left subtree

        root.left = self.build(preorder, pre_start + 1, pre_start + size,
                               postorder, post_start, idx)
        root.right = self.build(preorder, pre_start + size + 1, pre_end,
                                postorder, idx + 1, post_end - 1)
        return root

7Code line by line

8Dry run: watch all four indexes

index:        0  1  2  3  4  5  6
preorder  = [ 1, 2, 4, 5, 3, 6, 7 ]
postorder = [ 4, 5, 2, 6, 7, 3, 1 ]
pos = { 4:0, 5:1, 2:2, 6:3, 7:4, 3:5, 1:6 }

Each call is written as (pre_start, pre_end | post_start, post_end), the same way the teacher writes them on the board. Top row of boxes = preorder, bottom row = postorder. Yellow = this call's root, plain = inside the window, grey = outside.

Look at call 5: its postorder window starts at 3, not 0. That's the case from Doubt 2, and subtracting post_start is what gives the right size of 1.

The teacher's point about space: the call for 5 only enters the stack after the call for 4 has left it, so at any moment the stack holds about one call per level.

9Complexity & remember

• Time O(n): every node is created once, and each step does O(1) work thanks to the map. No nested loop.
• Space: the recursion stack holds one call per level, so it's O(h), where h is the height (levels on the longest root-to-leaf path). For a balanced tree h is about log n. For a skewed tree (every node has one child, so it's a straight line) h = n, so O(n). The hashmap also stores n entries, so the total extra space is O(n) either way.

Part B · Revision page

def preorder_of(node):
    return [node.val] + preorder_of(node.left) + preorder_of(node.right) if node else []

def postorder_of(node):
    return postorder_of(node.left) + postorder_of(node.right) + [node.val] if node else []

pre = [1, 2, 4, 5, 3, 6, 7]
post = [4, 5, 2, 6, 7, 3, 1]
root = Solution().constructFromPrePost(pre, post)
print(root.val, root.left.val, root.right.val)                 # 1 2 3
print(preorder_of(root) == pre, postorder_of(root) == post)    # True True
one = Solution().constructFromPrePost([1, 2], [2, 1])
print(one.left.val, one.right)                                 # 2 None

Based on this video: Construct Binary Tree from Preorder and Postorder Traversal