Algorithms & Coding Interviews · Recursion & Trees

Tree Traversals

Most binary-tree interview problems are DFS or BFS plus a small twist. Learn the four traversal orders, recursive and iterative templates, and the top-down vs bottom-up split, then watch traversal order, level-order BFS and Maximum Path Sum animated on real trees.

🧮 Algorithms & Coding Interviews● Intermediate⏱ 18 min read▶ 3 interactive🛠️ 4 exercises

🎯 What you'll learn

Preorder, inorder, postorder and level order
Recursive and iterative DFS, queue-based BFS
Top-down state vs bottom-up summaries (and both at once)
Six LeetCode problems up to Maximum Path Sum

📚 Before you start

Part 1The Pattern

Trees are where recursion feels most natural: a tree is a root plus two smaller trees. Almost every binary-tree interview problem is one of two traversals with a small twist: depth-first search (DFS: preorder, inorder, postorder), usually written recursively, or breadth-first search (BFS: level by level), written with a queue. The real skill is deciding what each recursive call returns and what information flows down vs up.

Preorder, inorder and postorder visit orders on the same tree

1The Node

python

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

typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val; this.left = left; this.right = right;
  }
}

LeetCode serializes trees in level order with nulls: [3,9,20,null,null,15,7] is a root 3 with children 9 and 20, and 20 has children 15 and 7.

2The Four Orders

Order	Visit	Typical use
Preorder	node → left → right	copy/serialize a tree, pass state down (path sums, depth)
Inorder	left → node → right	BST in sorted order, k-th smallest, validate BST
Postorder	left → right → node	compute from children up (height, diameter, subtree sums), delete a tree
Level order (BFS)	level by level	per-level answers (averages, right side view), shortest depth

3Templates

typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}
function _tree(level: (number | null)[]): TreeNode | null {
  if (!level.length || level[0] === null) return null;
  const root = new TreeNode(level[0]); const q: TreeNode[] = [root]; let i = 1;
  while (q.length && i < level.length) {
    const node = q.shift()!;
    if (i < level.length && level[i] !== null) { node.left = new TreeNode(level[i]!); q.push(node.left); }
    i++;
    if (i < level.length && level[i] !== null) { node.right = new TreeNode(level[i]!); q.push(node.right); }
    i++;
  }
  return root;
}
function _level(root: TreeNode | null): (number | null)[] {
  const out: (number | null)[] = []; const q: (TreeNode | null)[] = [root];
  while (q.length) { const n = q.shift()!; if (n) { out.push(n.val); q.push(n.left, n.right); } else out.push(null); }
  while (out.length && out[out.length - 1] === null) out.pop();
  return out;
}

function maxDepth(root: TreeNode | null): number {
  return root ? 1 + Math.max(maxDepth(root.left), maxDepth(root.right)) : 0;
}

function inorder(root: TreeNode | null): number[] {
  const out: number[] = [], stack: TreeNode[] = [];
  let node = root;
  while (stack.length || node) {
    while (node) { stack.push(node); node = node.left; }
    node = stack.pop()!;
    out.push(node.val);
    node = node.right;
  }
  return out;
}

function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const res: number[][] = [];
  let q: TreeNode[] = [root];
  while (q.length) {
    res.push(q.map((n) => n.val));
    q = q.flatMap((n) => [n.left, n.right].filter((c): c is TreeNode => c !== null));
  }
  return res;
}

function traversals(level: (number | null)[]): any[] {
  const root = _tree(level);
  return [maxDepth(root), inorder(root), levelOrder(root)];
}

python

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

def _tree(level):
    if not level or level[0] is None:
        return None
    root = TreeNode(level[0]); q = [root]; i = 1
    while q and i < len(level):
        node = q.pop(0)
        if i < len(level) and level[i] is not None:
            node.left = TreeNode(level[i]); q.append(node.left)
        i += 1
        if i < len(level) and level[i] is not None:
            node.right = TreeNode(level[i]); q.append(node.right)
        i += 1
    return root

def _level(root):
    out, q = [], [root]
    while q:
        n = q.pop(0)
        if n:
            out.append(n.val); q.append(n.left); q.append(n.right)
        else:
            out.append(None)
    while out and out[-1] is None:
        out.pop()
    return out

from collections import deque

def max_depth(root):                         # bottom-up: children report, parent combines
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

def inorder(root):                           # iterative DFS with an explicit stack
    out, stack, node = [], [], root
    while stack or node:
        while node:
            stack.append(node); node = node.left
        node = stack.pop()
        out.append(node.val)
        node = node.right
    return out

def level_order(root):                       # BFS, one level per loop iteration
    if not root:
        return []
    res, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
        res.append(level)
    return res

def traversals(level):
    root = _tree(level)
    return [max_depth(root), inorder(root), level_order(root)]

4Top-Down vs Bottom-Up

Top-down (preorder): pass information down as parameters: current depth, path sum so far, the allowed (low, high) range for BST validation. Answers are often collected in an outer variable at the leaves.
Bottom-up (postorder): each call returns a summary of its subtree (height, sum, "is balanced"), and the parent combines its children's summaries.

Some problems need both: Diameter and Maximum Path Sum return the best one-sided path upward, while updating a global answer with the best two-sided path through the current node. Recognizing that split is the key insight interviewers look for.

5Recursive vs Iterative

Recursion is shorter and clearer, but uses the call stack (O(h) for tree height h, which is O(n) for a skewed tree). Iterative DFS uses an explicit stack; iterative BFS uses a queue. Be ready to write the iterative inorder (the "go left as far as possible" loop above), as it's a common follow-up.

⚠️ Common Pitfalls

Missing the null check at the start of a recursive function.
Confusing height and depth (edges vs nodes; check what the problem counts).
BFS without fixing the level size: use for _ in range(len(q)) so you process exactly one level per iteration.
Returning the wrong thing in "global answer + return value" problems (return the one-sided path, store the two-sided one).
Using queue.shift() in JS inside BFS on big trees: O(n) per shift (swap queues per level instead).

📋 Quick Reference

text

DFS: if not node: return base; left = f(node.left); right = f(node.right); return combine(node, left, right)
BFS: q = [root]; while q: for _ in range(len(q)): node = q.popleft(); push children
Pre = state down · Post = summaries up · In = sorted order in a BST
O(n) time · O(h) stack for DFS · O(width) queue for BFS

Part 2Interview Problems

Six problems: bottom-up summaries (depth, diameter, max path sum), structural changes, BFS by level, and the classic LCA search.

1Maximum Depth of Binary Tree (LeetCode 104)

🟢 Easy. Return the number of nodes along the longest root-to-leaf path.

text

[3,9,20,null,null,15,7] → 3

Approach. Bottom-up: depth(node) = 1 + max(depth(left), depth(right)); an empty tree has depth 0.

Complexity. O(n) time, O(h) stack.

typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}
function _tree(level: (number | null)[]): TreeNode | null {
  if (!level.length || level[0] === null) return null;
  const root = new TreeNode(level[0]); const q: TreeNode[] = [root]; let i = 1;
  while (q.length && i < level.length) {
    const node = q.shift()!;
    if (i < level.length && level[i] !== null) { node.left = new TreeNode(level[i]!); q.push(node.left); }
    i++;
    if (i < level.length && level[i] !== null) { node.right = new TreeNode(level[i]!); q.push(node.right); }
    i++;
  }
  return root;
}
function _level(root: TreeNode | null): (number | null)[] {
  const out: (number | null)[] = []; const q: (TreeNode | null)[] = [root];
  while (q.length) { const n = q.shift()!; if (n) { out.push(n.val); q.push(n.left, n.right); } else out.push(null); }
  while (out.length && out[out.length - 1] === null) out.pop();
  return out;
}

function maxDepth(root: TreeNode | null): number {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

python

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

def _tree(level):
    if not level or level[0] is None:
        return None
    root = TreeNode(level[0]); q = [root]; i = 1
    while q and i < len(level):
        node = q.pop(0)
        if i < len(level) and level[i] is not None:
            node.left = TreeNode(level[i]); q.append(node.left)
        i += 1
        if i < len(level) and level[i] is not None:
            node.right = TreeNode(level[i]); q.append(node.right)
        i += 1
    return root

def _level(root):
    out, q = [], [root]
    while q:
        n = q.pop(0)
        if n:
            out.append(n.val); q.append(n.left); q.append(n.right)
        else:
            out.append(None)
    while out and out[-1] is None:
        out.pop()
    return out

def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

2Invert Binary Tree (LeetCode 226)

🟢 Easy. Mirror a binary tree (swap every node's left and right children) and return its root.

text

[4,2,7,1,3,6,9] → [4,7,2,9,6,3,1]

Approach. Swap the children of the current node and recurse into both (any traversal order works).

Complexity. O(n) time, O(h) stack.

typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}
function _tree(level: (number | null)[]): TreeNode | null {
  if (!level.length || level[0] === null) return null;
  const root = new TreeNode(level[0]); const q: TreeNode[] = [root]; let i = 1;
  while (q.length && i < level.length) {
    const node = q.shift()!;
    if (i < level.length && level[i] !== null) { node.left = new TreeNode(level[i]!); q.push(node.left); }
    i++;
    if (i < level.length && level[i] !== null) { node.right = new TreeNode(level[i]!); q.push(node.right); }
    i++;
  }
  return root;
}
function _level(root: TreeNode | null): (number | null)[] {
  const out: (number | null)[] = []; const q: (TreeNode | null)[] = [root];
  while (q.length) { const n = q.shift()!; if (n) { out.push(n.val); q.push(n.left, n.right); } else out.push(null); }
  while (out.length && out[out.length - 1] === null) out.pop();
  return out;
}

function invertTree(root: TreeNode | null): TreeNode | null {
  if (root) [root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
  return root;
}

python

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

def _tree(level):
    if not level or level[0] is None:
        return None
    root = TreeNode(level[0]); q = [root]; i = 1
    while q and i < len(level):
        node = q.pop(0)
        if i < len(level) and level[i] is not None:
            node.left = TreeNode(level[i]); q.append(node.left)
        i += 1
        if i < len(level) and level[i] is not None:
            node.right = TreeNode(level[i]); q.append(node.right)
        i += 1
    return root

def _level(root):
    out, q = [], [root]
    while q:
        n = q.pop(0)
        if n:
            out.append(n.val); q.append(n.left); q.append(n.right)
        else:
            out.append(None)
    while out and out[-1] is None:
        out.pop()
    return out

def invert_tree(root):
    if root:
        root.left, root.right = invert_tree(root.right), invert_tree(root.left)
    return root

3Binary Tree Level Order Traversal (LeetCode 102)

🟠 Medium. Return the node values level by level, left to right.

text

[3,9,20,null,null,15,7] → [[3],[9,20],[15,7]]

Approach. BFS with a queue. Each outer iteration processes exactly the nodes currently in the queue (one level), collecting their values and enqueueing their children.

Complexity. O(n) time, O(width) space.

typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}
function _tree(level: (number | null)[]): TreeNode | null {
  if (!level.length || level[0] === null) return null;
  const root = new TreeNode(level[0]); const q: TreeNode[] = [root]; let i = 1;
  while (q.length && i < level.length) {
    const node = q.shift()!;
    if (i < level.length && level[i] !== null) { node.left = new TreeNode(level[i]!); q.push(node.left); }
    i++;
    if (i < level.length && level[i] !== null) { node.right = new TreeNode(level[i]!); q.push(node.right); }
    i++;
  }
  return root;
}
function _level(root: TreeNode | null): (number | null)[] {
  const out: (number | null)[] = []; const q: (TreeNode | null)[] = [root];
  while (q.length) { const n = q.shift()!; if (n) { out.push(n.val); q.push(n.left, n.right); } else out.push(null); }
  while (out.length && out[out.length - 1] === null) out.pop();
  return out;
}

function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const res: number[][] = [];
  let level: TreeNode[] = [root];
  while (level.length) {
    res.push(level.map((n) => n.val));
    const next: TreeNode[] = [];
    for (const n of level) {
      if (n.left) next.push(n.left);
      if (n.right) next.push(n.right);
    }
    level = next;
  }
  return res;
}

python

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

def _tree(level):
    if not level or level[0] is None:
        return None
    root = TreeNode(level[0]); q = [root]; i = 1
    while q and i < len(level):
        node = q.pop(0)
        if i < len(level) and level[i] is not None:
            node.left = TreeNode(level[i]); q.append(node.left)
        i += 1
        if i < len(level) and level[i] is not None:
            node.right = TreeNode(level[i]); q.append(node.right)
        i += 1
    return root

def _level(root):
    out, q = [], [root]
    while q:
        n = q.pop(0)
        if n:
            out.append(n.val); q.append(n.left); q.append(n.right)
        else:
            out.append(None)
    while out and out[-1] is None:
        out.pop()
    return out

from collections import deque

def level_order(root):
    if not root:
        return []
    res, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
        res.append(level)
    return res

4Diameter of Binary Tree (LeetCode 543)

🟢 Easy. Return the length (in edges) of the longest path between any two nodes.

text

[1,2,3,4,5] → 3   (path 4-2-1-3 or 5-2-1-3)

Approach. Postorder: each call returns its height; at each node, the longest path through it is leftHeight + rightHeight, which updates a global maximum. The path doesn't have to pass through the root.

Complexity. O(n) time, O(h) stack.

typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}
function _tree(level: (number | null)[]): TreeNode | null {
  if (!level.length || level[0] === null) return null;
  const root = new TreeNode(level[0]); const q: TreeNode[] = [root]; let i = 1;
  while (q.length && i < level.length) {
    const node = q.shift()!;
    if (i < level.length && level[i] !== null) { node.left = new TreeNode(level[i]!); q.push(node.left); }
    i++;
    if (i < level.length && level[i] !== null) { node.right = new TreeNode(level[i]!); q.push(node.right); }
    i++;
  }
  return root;
}
function _level(root: TreeNode | null): (number | null)[] {
  const out: (number | null)[] = []; const q: (TreeNode | null)[] = [root];
  while (q.length) { const n = q.shift()!; if (n) { out.push(n.val); q.push(n.left, n.right); } else out.push(null); }
  while (out.length && out[out.length - 1] === null) out.pop();
  return out;
}

function diameterOfBinaryTree(root: TreeNode | null): number {
  let best = 0;
  const height = (node: TreeNode | null): number => {
    if (!node) return 0;
    const lh = height(node.left), rh = height(node.right);
    best = Math.max(best, lh + rh);
    return 1 + Math.max(lh, rh);
  };
  height(root);
  return best;
}

python

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

def _tree(level):
    if not level or level[0] is None:
        return None
    root = TreeNode(level[0]); q = [root]; i = 1
    while q and i < len(level):
        node = q.pop(0)
        if i < len(level) and level[i] is not None:
            node.left = TreeNode(level[i]); q.append(node.left)
        i += 1
        if i < len(level) and level[i] is not None:
            node.right = TreeNode(level[i]); q.append(node.right)
        i += 1
    return root

def _level(root):
    out, q = [], [root]
    while q:
        n = q.pop(0)
        if n:
            out.append(n.val); q.append(n.left); q.append(n.right)
        else:
            out.append(None)
    while out and out[-1] is None:
        out.pop()
    return out

def diameter_of_binary_tree(root):
    best = 0

    def height(node):
        nonlocal best
        if not node:
            return 0
        lh, rh = height(node.left), height(node.right)
        best = max(best, lh + rh)            # path through this node
        return 1 + max(lh, rh)               # height reported to the parent

    height(root)
    return best

5Lowest Common Ancestor of a Binary Tree (LeetCode 236)

🟠 Medium. Given two nodes p and q in a binary tree, return their lowest common ancestor (a node can be its own ancestor).

text

root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 → 3

Approach. Postorder search: return the node if it is p or q; otherwise recurse left and right. If both sides return something, the current node is the LCA; if only one side does, pass that result up.

Complexity. O(n) time, O(h) stack.

typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}
function _tree(level: (number | null)[]): TreeNode | null {
  if (!level.length || level[0] === null) return null;
  const root = new TreeNode(level[0]); const q: TreeNode[] = [root]; let i = 1;
  while (q.length && i < level.length) {
    const node = q.shift()!;
    if (i < level.length && level[i] !== null) { node.left = new TreeNode(level[i]!); q.push(node.left); }
    i++;
    if (i < level.length && level[i] !== null) { node.right = new TreeNode(level[i]!); q.push(node.right); }
    i++;
  }
  return root;
}
function _level(root: TreeNode | null): (number | null)[] {
  const out: (number | null)[] = []; const q: (TreeNode | null)[] = [root];
  while (q.length) { const n = q.shift()!; if (n) { out.push(n.val); q.push(n.left, n.right); } else out.push(null); }
  while (out.length && out[out.length - 1] === null) out.pop();
  return out;
}

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
  if (!root || root === p || root === q) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root;
  return left ?? right;
}

python

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

def _tree(level):
    if not level or level[0] is None:
        return None
    root = TreeNode(level[0]); q = [root]; i = 1
    while q and i < len(level):
        node = q.pop(0)
        if i < len(level) and level[i] is not None:
            node.left = TreeNode(level[i]); q.append(node.left)
        i += 1
        if i < len(level) and level[i] is not None:
            node.right = TreeNode(level[i]); q.append(node.right)
        i += 1
    return root

def _level(root):
    out, q = [], [root]
    while q:
        n = q.pop(0)
        if n:
            out.append(n.val); q.append(n.left); q.append(n.right)
        else:
            out.append(None)
    while out and out[-1] is None:
        out.pop()
    return out

def lowest_common_ancestor(root, p, q):
    if not root 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:
        return root                      # p and q are on different sides
    return left or right

6Binary Tree Maximum Path Sum (LeetCode 124)

🔴 Hard. A path is any sequence of connected nodes (each used once, not necessarily through the root). Return the maximum path sum. Values may be negative.

text

[-10,9,20,null,null,15,7] → 42   (15 → 20 → 7)

Approach. Postorder. gain(node) returns the best sum of a path that starts at node and goes down one side: node.val + max(0, gain(left), gain(right)) (negative branches are dropped with max(0, …)). At each node, the best path through it is node.val + max(0, gainL) + max(0, gainR), which updates the global answer.

Complexity. O(n) time, O(h) stack.

typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}
function _tree(level: (number | null)[]): TreeNode | null {
  if (!level.length || level[0] === null) return null;
  const root = new TreeNode(level[0]); const q: TreeNode[] = [root]; let i = 1;
  while (q.length && i < level.length) {
    const node = q.shift()!;
    if (i < level.length && level[i] !== null) { node.left = new TreeNode(level[i]!); q.push(node.left); }
    i++;
    if (i < level.length && level[i] !== null) { node.right = new TreeNode(level[i]!); q.push(node.right); }
    i++;
  }
  return root;
}
function _level(root: TreeNode | null): (number | null)[] {
  const out: (number | null)[] = []; const q: (TreeNode | null)[] = [root];
  while (q.length) { const n = q.shift()!; if (n) { out.push(n.val); q.push(n.left, n.right); } else out.push(null); }
  while (out.length && out[out.length - 1] === null) out.pop();
  return out;
}

function maxPathSum(root: TreeNode | null): number {
  let best = -Infinity;
  const gain = (node: TreeNode | null): number => {
    if (!node) return 0;
    const left = Math.max(0, gain(node.left)), right = Math.max(0, gain(node.right));
    best = Math.max(best, node.val + left + right);
    return node.val + Math.max(left, right);
  };
  gain(root);
  return best;
}

python

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

def _tree(level):
    if not level or level[0] is None:
        return None
    root = TreeNode(level[0]); q = [root]; i = 1
    while q and i < len(level):
        node = q.pop(0)
        if i < len(level) and level[i] is not None:
            node.left = TreeNode(level[i]); q.append(node.left)
        i += 1
        if i < len(level) and level[i] is not None:
            node.right = TreeNode(level[i]); q.append(node.right)
        i += 1
    return root

def _level(root):
    out, q = [], [root]
    while q:
        n = q.pop(0)
        if n:
            out.append(n.val); q.append(n.left); q.append(n.right)
        else:
            out.append(None)
    while out and out[-1] is None:
        out.pop()
    return out

def max_path_sum(root):
    best = float("-inf")

    def gain(node):
        nonlocal best
        if not node:
            return 0
        left = max(0, gain(node.left))
        right = max(0, gain(node.right))
        best = max(best, node.val + left + right)   # path bending at this node
        return node.val + max(left, right)          # one side only, for the parent

    gain(root)
    return best

🧠 Key takeaways

DFS (pre/in/post) by recursion; BFS by queue, one level per iteration.
Top-down passes state down as parameters; bottom-up returns subtree summaries.
Diameter / max path sum: return one side, record both sides in a global answer.
DFS uses O(h) stack (O(n) when skewed); know the iterative inorder as a follow-up.

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

algo_tree_traversals_exercise_1.py

TS PY

algo_tree_traversals_exercise_2.py

TS PY

✅ Check yourself

Answer the questions — feedback is instant.

1. Which traversal of a BST yields sorted order?

left → node → right.

2. Height of a subtree is computed best with…

Bottom-up summary.

3. In Maximum Path Sum, what does the recursive function return?

Parents can only extend one side.

4. Why loop for _ in range(len(q)) in BFS?

Level boundaries.

Source: algo_tree_traversals_theory_1.md, algo_tree_traversals_theory_2.md · generated by tools/build_lessons.py