mediumDSA

How do you build a binary tree from preorder and inorder traversals?

Q: How do you build a binary tree from preorder and inorder traversals?

**Intuition.** **Preorder** gives you roots in the order root-first; **inorder** tells you, for any root, which values fall to its left vs its right. So: take the next preorder value as the current root, locate it in inorder to split the remaining values into left and right halves, and recurse. preorder[0]=3 is root; split inorder around it preorder: 3 9 20 15 7 inorder: 9

179 views

Understand the problem

Explain tree reconstruction.

treesconstruction

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

Read the code

Preorder pointer + inorder index map

Run Playground

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def build_tree(preorder, inorder):
    idx = {v: i for i, v in enumerate(inorder)}
    pos = [0]
    def build(lo, hi):
        if lo > hi:
            return None
        root_val = preorder[pos[0]]
        pos[0] += 1
        node = TreeNode(root_val)
        mid = idx[root_val]
        node.left = build(lo, mid - 1)
        node.right = build(mid + 1, hi)
        return node
    return build(0, len(inorder) - 1)


# --- demo ---  rebuild, then re-emit preorder to confirm round-trip
def preorder_of(node, out):
    if node:
        out.append(node.val)
        preorder_of(node.left, out)
        preorder_of(node.right, out)
    return out

tree = build_tree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7])
print(preorder_of(tree, []))   # [3, 9, 20, 15, 7]

Join the discussion

Discussion (0)

No responses yet. Be the first to share what you think.

What is the two-pointer technique?

What are the tree traversal methods?