leetExpert

Module 17 · Binary Trees

Practice

Practice~2 min

How to practice this module

Tree drills reward choosing the traversal that carries the answer: depth and diameter are bottom-up returns, level-order is a BFS queue, reconstruction splits by the inorder root, and LCA combines both. Done when all seven show Solved in the hub.

Problems

Binary Trees — work them in order; difficulty ascends.

0/7

solved

  1. 1Maximum Depth of Binary TreeEasyBottom-up heightWatch for: Base null -> 0; height = 1 + max(left, right) — count nodes or edges consistently
  2. 2Diameter of Binary TreeEasyPost-order + globalWatch for: The diameter can skip the root — track the max left+right path anywhere in the tree, not just at the root
  3. 3Binary Tree Level Order TraversalMediumBFS level drainWatch for: Drain exactly size nodes per level; a single queue plus per-level sizing is the whole technique
  4. 4Construct Binary Tree from Preorder and Inorder TraversalMediumSplit by inorder rootWatch for: Preorder gives the root, inorder tells the split — recurse by index spans (lengths), never by global positions
  5. 5Lowest Common Ancestor of a Binary TreeMediumPost-order presenceWatch for: If left and right both report a target, this node is the LCA; otherwise propagate whichever side found one
  6. 6Binary Tree Right Side ViewMediumBFS rightmost per levelWatch for: Record the last node of each level; a depth-first visit also works if you overwrite the slot per depth
  7. 7Serialize and Deserialize Binary TreeHardPreorder with nullsWatch for: Emit a marker for null children so the shape is recoverable — a value-only stream loses structure

Cheatsheet

Binary Trees — Rooted structure — traverse with intent (order, level, or path).

Smell → pattern

  • Visit every node onceDFS pre/in/post
  • Per level aggregatesBFS queue
  • Path / diameter styleDFS return + global
  • Reconstruct from traversalsSplit by inorder root

Patterns

Recursive DFS

Core

Smell: Combine children with the root

Base null → 0/identity. Combine left and right with the root. Pick pre/in/post for when you use the root value.

Level-order BFS

Safe

Smell: Averages, zigzags, right-side view

Queue nodes; drain a level size each round. Natural for averages, zigzags, and ‘right side view’.

0L1L2

Post-order aggregate

Reach

Smell: Height, diameter, LCA prep

Need both children before deciding. Compute below, then update a global answer — don’t decide too early.

Reconstruct from traversals

Careful

Smell: Preorder + inorder (or the like)

Take the root from preorder, split inorder into left/right spans, recurse on each span. The root index bookkeeping is the entire trap.

Complexity targets

  • DFS / BFS visit

    Time
    O(n)
    Space
    O(h) / O(w)
    Note
    h height, w width

  • Path aggregates

    Time
    O(n)
    Space
    O(h)
    Note
    One pass with returns

  • Reconstruct

    Time
    O(n)
    Space
    O(n)
    Note
    With index map

Traps

  • Null child assumptions

    Always guard left/right. Many ‘simple’ bugs are dereferencing null on a leaf’s child.

  • Confusing node count with height

    Height and depth conventions differ (edges vs nodes). Pick one definition and stick to it in base cases.

  • Reconstruction index drift

    Inorder split sizes shrink each level; recompute spans from lengths, not from global positions, or you read off the wrong subtree.