λDSA Learning Hubpart of DSA Atlas

Binary Trees

Intermediate~4h · 9 lessons12 practice problems

At most two children per node — and the traversal toolkit (pre/in/post/level order), height, diameter, LCA, and view problems built on it.

0 of 9 lessons checked off

Introduction

What it is

  • A binary tree caps every node at two children — left and right, and the distinction matters. It adds no ordering rule (that's the BST's job); it's pure structure.
  • Its superpower is that every node splits the world in two, which makes divide-and-conquer natural and gives four canonical traversal orders.

Why it matters

  • Binary trees are the most-asked interview data structure after arrays: traversals, height/diameter, symmetry, lowest common ancestor, and serialization are permanent fixtures.
  • They're also the parent class of workhorses: BSTs (ordered), heaps (complete + ordered by priority), and expression trees (operators over operands).

How it works

  • DFS traversals differ only in WHEN the node is processed relative to its subtrees: pre (node first), in (between), post (after). BFS (level order) uses a queue instead of recursion.
  • Most problems reduce to: get answers from left and right subtrees, combine with the node, return upward. Choosing the traversal = choosing when 'combine' runs.

Where it's used

  • Expression trees evaluate formulas in compilers and calculators; Huffman coding trees compress files; binary space partitioning renders game scenes.

In interviews

  • Max depth, diameter, invert, symmetric, level-order grouping, zigzag, right/left views, LCA, serialize/deserialize, path sums — the core FAANG set.
Analogy: A tournament bracket: every match (node) feeds two earlier matches (children). Traversals are different ways to read the bracket: announce the final first (preorder) or crown it last (postorder).

Interactive diagram

Inorder shown here (Left–Root–Right); the operations below animate the others on the same tree.

147631314108
Inorder traversal

Visit the left subtree, then the node, then the right subtree (Left–Root–Right). On a BST this yields sorted order.

Lessons in this topic

Check off lessons as you go — your progress is saved in this browser.

  1. Binary tree structure and construction

    TreeNode, left vs right, building from lists.

    15 min
  2. Preorder, inorder, postorder (recursive)

    One template, three positions for the visit.

    30 min
  3. Iterative traversal with a stack

    Making the call stack explicit; inorder's push-left spine.

    25 min
  4. Level-order traversal

    Queue + level-size snapshots; views and zigzags.

    20 min
  5. Height, depth, and diameter

    Postorder aggregation; diameter as max(left h + right h + 2).

    25 min
  6. Invert, symmetric, and same-tree

    Mirroring and simultaneous recursion on two trees.

    20 min
  7. Lowest common ancestor

    The 'first node where paths split' — postorder logic.

    25 min
  8. Views and vertical order

    Left/right/top/bottom views from level order + column indexing.

    20 min
  9. Serialize and deserialize

    Preorder with None markers round-trips any tree.

    20 min

Operations

Preorder traversal (Root–Left–Right)

Process the node BEFORE its subtrees — the order that copies and serializes trees.

147631314108
Preorder traversal

Visit the node first, then its left subtree, then its right subtree (Root–Left–Right). Used to copy or serialize a tree.

def preorder(root, visit):    if root is None:        return    visit(root.val)          # node first    preorder(root.left, visit)    preorder(root.right, visit)
Time: O(n)Space: O(h) stack

Edge cases

  • Empty tree: nothing visited.
  • Preorder + None markers uniquely reconstructs a tree (serialization).
  • Preorder of a BST is enough to rebuild it (values encode structure).

Common mistakes

  • Confusing preorder with 'top-down BFS' — preorder dives, BFS sweeps levels.
  • Visiting after the recursive calls (that's postorder).

Inorder traversal (Left–Root–Right)

Process between the subtrees. On a BST this emits values in sorted order — the single most quoted tree fact.

147631314108
Inorder traversal

Visit the left subtree, then the node, then the right subtree (Left–Root–Right). On a BST this yields sorted order.

def inorder_iterative(root) -> list[int]:    """Explicit-stack inorder: push the left spine, pop, go right."""    out: list[int] = []    stack: list = []    node = root    while node or stack:        while node:                  # dive down the left spine            stack.append(node)            node = node.left        node = stack.pop()           # leftmost unvisited        out.append(node.val)         # visit        node = node.right            # then its right subtree    return out
Time: O(n)Space: O(h)

Edge cases

  • BST + inorder = sorted output; use it to validate BSTs and find kth smallest.
  • Right-skewed trees never push — the outer loop still terminates via stack emptiness.
  • Both `node` and `stack` empty is the only exit.

Common mistakes

  • Popping before fully diving left — visits parents too early.
  • while stack (alone) as the loop condition — misses the initial dive.

Postorder traversal (Left–Right–Root)

Process AFTER both subtrees — the order of deletion, subtree sums, and every 'combine children's answers' problem.

147631314108
Postorder traversal

Visit both subtrees before the node (Left–Right–Root). Used to delete a tree or compute subtree aggregates.

def diameter(root) -> int:    """Longest path (edges) between any two nodes — postorder in action."""    best = 0    def height(node) -> int:        nonlocal best        if node is None:            return -1        left = height(node.left)      # children first...        right = height(node.right)        best = max(best, left + right + 2)   # ...then combine at the node        return 1 + max(left, right)    height(root)    return best
Time: O(n)Space: O(h)

Edge cases

  • The diameter path need not pass through the root — that's why best updates at EVERY node.
  • Single node: diameter 0.
  • Return height, track diameter separately — mixing them up is the classic bug.

Common mistakes

  • Computing diameter as root's left height + right height only.
  • Recomputing height inside diameter recursively — O(n²); compute both in one postorder pass.

Level-order traversal (BFS)

A queue visits nodes distance by distance. Snapshotting the queue length gives per-level grouping — the key to views and zigzags.

147631314108
Levelorder traversal

Visit nodes level by level using a queue (BFS). Used for shortest paths in unweighted structures and level grouping.

from collections import dequedef level_order(root) -> list[list[int]]:    """Values grouped by level. O(n) time, O(width) space."""    if root is None:        return []    levels: list[list[int]] = []    queue = deque([root])    while queue:        level_size = len(queue)          # snapshot BEFORE the loop        level: list[int] = []        for _ in range(level_size):            node = queue.popleft()            level.append(node.val)            if node.left:                queue.append(node.left)            if node.right:                queue.append(node.right)        levels.append(level)    return levels
Time: O(n)Space: O(max width) — up to n/2 for the last level

Edge cases

  • Empty tree returns [] not [[]].
  • Right view = last element of each level; left view = first.
  • Zigzag = reverse alternate levels after collection.

Common mistakes

  • Reading len(queue) inside the for condition while appending children — the level boundary dissolves.
  • Using a list with pop(0) as the queue: O(n²).

Lowest common ancestor

Recurse both sides; a node that sees the targets in different subtrees (or is itself one of them) is the answer.

Lowest common ancestor
def lowest_common_ancestor(root, p, q):    """LCA in a plain binary tree. O(n) time, O(h) space."""    if root is None or root is p or root is q:        return root    left = lowest_common_ancestor(root.left, p, q)    right = lowest_common_ancestor(root.right, p, q)    if left and right:        # p and q split here — this is the LCA        return root    return left or right      # bubble up whichever side found something
Time: O(n)Space: O(h)

Edge cases

  • A node is its own ancestor: LCA(p, p's descendant) = p — handled by the early return.
  • Assumes both nodes exist in the tree; say so, or verify existence first.
  • Compare node IDENTITY, not values (duplicates).

Common mistakes

  • Returning values instead of nodes and losing identity.
  • Trying to collect root-to-node paths first — works (O(n) extra space) but the direct recursion is the expected answer.

Complexity analysis

OperationBestAverageWorstSpace
Any full traversal (DFS/BFS)O(n)O(n)O(n)O(h) / O(width)
Height / diameter / symmetricO(n)O(n)O(n)O(h)
Search (no ordering)O(1)O(n)O(n)O(h)
LCA (single query)O(n)O(n)O(n)O(h)
Serialize / deserializeO(n)O(n)O(n)O(n)

Plain binary trees have no order, so anything 'find'-shaped is O(n). Ordering (BST) or shape guarantees (heap) are what buy speed.

Python implementation

Production-quality code with type hints, validation, and docstrings.

Serialize and deserialize (preorder + None markers)
from typing import Optionalclass TreeNode:    def __init__(self, val: int = 0, left=None, right=None):        self.val, self.left, self.right = val, left, rightdef serialize(root: Optional[TreeNode]) -> str:    """Preorder with '#' for None — uniquely encodes the structure."""    parts: list[str] = []    def walk(node: Optional[TreeNode]) -> None:        if node is None:            parts.append("#")            return        parts.append(str(node.val))        walk(node.left)

What interviewers expect you to know

What interviewers expect you to know

  • All four traversals, recursive AND iterative-inorder, without warm-up.
  • The postorder pattern: return info upward, combine at the node — height, diameter, balanced-check, path sums all reuse it.
  • Level-size snapshotting for anything phrased 'per level' or 'view'.
  • BST inorder = sorted — even on the plain binary-tree page, because follow-ups pivot on it.

Classic follow-ups

  • "Do it iteratively" (after any recursive traversal) — the stack version, and knowing WHY (recursion limits, explicit control).
  • "O(1) space traversal?" — Morris traversal exists via threaded trees; name it, don't derive it.
  • "Diameter in one pass?" — height recursion with a nonlocal best; avoid the O(n²) recompute.
  • "Which traversals reconstruct a tree?" — in+pre, in+post (unique with distinct values); pre+post alone is ambiguous.

How to talk through tree problems

  • Open with the contract: 'my function returns the height of this subtree' — then the combine step writes itself.
  • Name the traversal you're choosing and why: 'per-level output → BFS with size snapshots'.

Common mistakes

Height vs depth confusion

Diameter, balance checks and 'max depth' all break if you measure from the wrong end. Depth: from root. Height: to leaves.

The O(n²) diameter

Calling height() inside a separate diameter() recursion recomputes heights at every node. Fold both into one postorder pass.

Level boundaries dissolved

BFS without snapshotting len(queue) merges levels — right view and zigzag silently return wrong answers.

Wrong base case

Returning 0 for None when the convention needs −1 (edge-counting height) shifts every answer by one.

Identity vs equality

LCA and same-tree problems compare nodes with ==; duplicates then lie. Use `is` for node identity.

Missing the None check first

Every recursive tree function starts `if root is None:` — skipping it crashes on leaves' children.

Practice problems

Hand-picked from the 355-problem DSA Atlas. Reveal hints and solutions progressively; mark and bookmark as you solve.

Easy (5)

Medium (5)

Hard (2)

Topic quiz

6 questions across concepts, code output, complexity, and scenarios. Answer all, then submit for explanations.

  1. Code output1. For the tree 8(3(1,6),10(#,14)), what does inorder traversal output?
  2. Concept2. Which traversal must you use to DELETE every node of a tree safely (children before parent)?
  3. Code output3. What does this compute?
    def f(node):    if node is None:        return 0    return 1 + max(f(node.left), f(node.right))
  4. Scenario4. You need the rightmost node of every level. Cheapest correct approach?
  5. Concept5. In the standard LCA recursion, root is the LCA when…
  6. Complexity6. Level-order traversal's worst-case queue size on a complete binary tree of n nodes is about…
0 of 6 answered

Frequently asked questions

How do I choose between DFS and BFS on a tree?

Phrased per-level, by distance, or 'view' → BFS. Aggregating subtree information (heights, sums, balance) → DFS postorder. Path-from-root problems → DFS preorder carrying state down.

Which two traversals uniquely rebuild a tree?

Inorder + preorder, or inorder + postorder (with distinct values). Preorder + postorder alone is ambiguous for single-child nodes. Alternatively, ONE traversal with explicit None markers suffices — that's serialization.

Is Morris traversal worth learning?

Know it exists: inorder in O(1) space by temporarily threading right pointers. Interviews rarely require implementation; naming the trade-off (mutates the tree during traversal) is usually full credit.

Summary & cheat sheet

Key takeaways

  • Traversal choice = when the node is processed: pre (before), in (between), post (after), level (by distance).
  • Postorder aggregation — return child answers, combine at the node — solves the height/diameter/balance family.
  • BFS + len(queue) snapshot = per-level everything.
  • LCA: the node where the two searches split.
  • Preorder + None markers serializes any binary tree uniquely.

Formulas & cheat sheet

  • diameter(node) candidates: leftHeight + rightHeight + 2 (edge convention)
  • Nodes at depth d ≤ 2^d; last level of complete tree ≈ n/2
  • Reconstruction: inorder + (pre|post)order → unique tree

Interview checklist

  • I can write all four traversals, plus iterative inorder.
  • I can compute diameter in a single pass.
  • I can produce right/left views with BFS snapshots.
  • I can implement LCA and serialize/deserialize.