Sign in
Skip to solution
mediumDSA

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

179 views
01

Understand the problem

Explain tree reconstruction.

treesconstruction
02

Attempt it yourself

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

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

The first preorder element is the root; find it in the inorder array to split left/right subtrees, then recurse. Use a hashmap of inorder indices and a moving preorder pointer for O(n) instead of O(n²) searching.

Solution ready — 2 min read

Classified // press E to declassify

04

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]
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

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

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 93 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track