Trees

Tree Construction & Serialization

Rebuild a tree from traversals, or encode a tree as a string and decode it back.

Medium, about 90 minutes to practise.

1Understand

The idea

A preorder traversal tells you the root first; the inorder traversal then splits the remaining values into the left and right subtrees. Recurse on each side, using a dict from value to inorder index so each split is O(1). Serialization is the same idea in reverse: write the traversal with markers for empty children.

Intuition

Preorder tells you the root first; inorder then splits the remaining values into left and right subtrees. Recurse on each side. A dict from value to inorder index makes each split O(1) instead of scanning.

Postorder + inorder is the same idea with the root at the end of the postorder slice. Serialization writes a traversal with null markers so you can parse uniquely later.

The recursive structure of the tree is exactly the recursive structure of the build.

What you will be able to do

  • Use one traversal for roots and inorder for splits
  • Encode None markers so the tree is unambiguous

When to use it

  • Given preorder and inorder (or postorder)
  • Serialize / deserialize
  • Build a tree from a list or string

2See it

Walkthrough

Build from preorder + inorder

pre=[3,9,20], in=[9,3,20], root is pre[0]; split inorder.

1 / 5

i
3
9
20
012
i → index 0

Preorder root = 3. Inorder index of 3 splits left keys from right keys.

root = TreeNode(preorder[0])

Live template

Line 1 active

1index = {v: i for i, v in enumerate(inorder)}
2def build(lo, hi):
3 if lo > hi: return None
4 root = TreeNode(next(pre))
5 mid = index[root.val]
6 root.left, root.right = build(lo, mid - 1), build(mid + 1, hi)
7 return root

Complexity: time O(n), space O(n)

Time O(n) with the index map; O(n²) if each split scans inorder. Space O(n) for the map and O(h) recursion. Serialization/deserialization is O(n); choose a format (preorder with nulls) that preserves structure.

Read the walkthrough as text

Build from preorder and inorder. preorder = [3,9,20,15,7], inorder = [9,3,15,20,7].

  1. Root is 3 (first preorder). In inorder, left of 3 is [9], right is [15,20,7].
  2. Next preorder chunk of size 1 builds left child 9.
  3. Remaining preorder [20,15,7] builds the right subtree with root 20, and so on.

In code:

  • idx = {v: i for i, v in enumerate(inorder)}
  • # recurse with preorder bounds and inorder lo/hi

3Recognise it

Kinds of problems (6)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Preorder + inorder

    Example. Rebuild tree from preorder and inorder traversals.

    How. Next preorder is root; inorder index map splits left/right ranges recursively.

  • Postorder + inorder

    Example. Construct from postorder and inorder.

    How. Root is last postorder element; split inorder at root and recurse on subranges.

  • Serialize / deserialize (preorder with markers)

    Example. Encode tree to string and decode back.

    How. Pre-order with explicit “null” tokens so shape is recoverable.

  • Level-order serialization

    Example. Serialize by BFS layers with null slots.

    How. Enqueue children even when null until trailing nulls trimmed on decode.

  • Sorted array to balanced BST

    Example. Minimal height BST from sorted nums.

    How. Same mid-root divide on index ranges, construction without traversal lists.

  • Build from parent–child descriptions

    Example. Given parent array, wire children under each parent.

    How. Map value→node; for each i, attach i to parent[i] as left or right by rule or index parity.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Linear root search

    Why it happens. Scanning inorder for each root is simple and avoids extra memory.

    How it fails. n nodes, each root scans O(n), O(n²) construction times out on 10⁴ nodes.

    Fix. Precompute value → inorder index map once; O(1) split per root.

  • Ambiguous encoding

    Why it happens. Serializing only values feels enough if roots imply structure.

    How it fails. Preorder "1,2" could be root+left or root+right, decode rebuilds the wrong shape.

    Fix. Encode None explicitly so preorder uniquely determines shape.

  • Wrong build order

    Why it happens. Building the right subtree first matches reading preorder left-to-right visually.

    How it fails. Consume preorder for right before left, left subtree never gets its roots in order.

    Fix. Always build left subtree range first, then right, matching how preorder is consumed.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons