Study Notes by Niladri & AI

Session-06-Trees

Properties1
tagstrees, dfs, bfs, binary-tree, interview-prep, java

13 min read

Practice Session 6: Trees — DFS and BFS

Overview

Binary tree problems appear in roughly 25% of senior-level technical interviews and map directly to real engineering systems: file hierarchies, org charts, DOM trees, distributed query plans. The key senior insight is knowing which traversal order matches the problem’s dependency structure — preorder (top-down), postorder (bottom-up aggregation), or BFS (level isolation). Null-checking discipline and the distinction between “return value to parent” vs “update global state” separate mediocre answers from strong ones.

Problem 1: Maximum Depth of Binary Tree

Link: LeetCode 104

Quick Summary: Given the root of a binary tree, return its maximum depth (number of nodes along the longest root-to-leaf path).

Industry Context: Container orchestration (Kubernetes) computes the longest dependency chain of init-containers to determine worst-case startup latency — exact same postorder depth aggregation. Also: DOM nesting depth for CSS specificity, recursive directory depth for filesystem quota enforcement.

Approach 1: Recursive DFS (postorder)

// Time: O(n)  Space: O(h) — h = height of tree
public int maxDepthRecursive(TreeNode root) {
    if (root == null) return 0;
    int leftDepth  = maxDepthRecursive(root.left);
    int rightDepth = maxDepthRecursive(root.right);
    return 1 + Math.max(leftDepth, rightDepth);
}
  • Time: O(n) — every node visited once
  • Space: O(h) — recursion stack; O(log n) balanced, O(n) skewed
  • Tradeoff: Clean and idiomatic. Risk: stack overflow on very deep trees (10k+ levels in production). Use iterative BFS when tree depth is unbounded.

Approach 2: Iterative BFS (level counting)

// Time: O(n)  Space: O(w) — w = max width of tree
public int maxDepthBFS(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int depth = 0;
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        depth++;
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            if (node.left  != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
    return depth;
}
  • Time: O(n)
  • Space: O(w) — at most n/2 nodes in queue for a perfect binary tree
  • Key Insight: BFS naturally processes nodes by level. Snapshotting queue.size() before the inner loop isolates each level. The depth counter simply counts how many levels we drain — no arithmetic needed.

Problem 2: Invert Binary Tree

Link: LeetCode 226

Quick Summary: Mirror a binary tree by swapping every node’s left and right children.

Industry Context: Rendering engines flip subtrees for RTL (right-to-left) locale support — the DOM subtree is structurally inverted. Also appears in distributed merge logic: when two replicas diverge in child ordering, a structural inversion reconciles them.

Approach 1: Recursive DFS (postorder)

// Time: O(n)  Space: O(h)
public TreeNode invertTreeRecursive(TreeNode root) {
    if (root == null) return null;
    TreeNode invertedLeft  = invertTreeRecursive(root.left);
    TreeNode invertedRight = invertTreeRecursive(root.right);
    root.left  = invertedRight;
    root.right = invertedLeft;
    return root;
}
  • Time: O(n)
  • Space: O(h)
  • Tradeoff: Postorder guarantees children are fully resolved before the parent’s swap. Using preorder (swap before recursing) also works and can feel more intuitive — both are valid here.

Approach 2: Iterative BFS

// Time: O(n)  Space: O(w)
public TreeNode invertTreeBFS(TreeNode root) {
    if (root == null) return null;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        // Swap children
        TreeNode temp  = node.left;
        node.left  = node.right;
        node.right = temp;
        if (node.left  != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
    return root;
}
  • Time: O(n)
  • Space: O(w)
  • Key Insight: Swap at each dequeued node, then enqueue the (now-swapped) children. Order of enqueuing doesn’t matter because we process every node unconditionally — no level-level coordination needed, unlike level-order traversal.

Problem 3: Binary Tree Level Order Traversal

Link: LeetCode 102

Quick Summary: Return a list of lists where each inner list contains the values of nodes at that depth level, left to right.

Industry Context: BFS level-order is the backbone of “shortest path in org hierarchies” — finding the minimum number of reporting hops between two employees. Also used in game AI (BFS game tree evaluation by ply/depth), and in distributed systems for wave propagation (barrier synchronization where all nodes at level k must complete before level k+1 starts).

Approach 1: DFS with depth tracking (naive)

// Time: O(n)  Space: O(h) call stack + O(n) output
public List<List<Integer>> levelOrderDFS(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    dfsHelper(root, 0, result);
    return result;
}
 
private void dfsHelper(TreeNode node, int depth, List<List<Integer>> result) {
    if (node == null) return;
    if (depth == result.size()) {
        result.add(new ArrayList<>());   // first time we reach this depth
    }
    result.get(depth).add(node.val);
    dfsHelper(node.left,  depth + 1, result);
    dfsHelper(node.right, depth + 1, result);
}
  • Time: O(n)
  • Space: O(h) recursion + O(n) output
  • Tradeoff: Correct but non-intuitive — DFS visiting nodes in preorder produces the right level buckets only because we always go left before right. Hard to reason about in interviews; prefer BFS.

Approach 2: BFS with level segmentation (optimal / idiomatic)

// Time: O(n)  Space: O(w) queue
public List<List<Integer>> levelOrderBFS(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int levelSize = queue.size();          // snapshot current level count
        List<Integer> currentLevel = new ArrayList<>();
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            currentLevel.add(node.val);
            if (node.left  != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(currentLevel);
    }
    return result;
}
  • Time: O(n)
  • Space: O(w) — O(n/2) ≈ O(n) for a perfect binary tree’s last level
  • Key Insight: The “snapshot queue.size() before the inner loop” trick is the entire template for BFS level separation. Children enqueued during level k are never touched until level k+1’s iteration begins, because the inner loop runs exactly levelSize times. Memorize this template — it solves LC 102, 107, 199, 513, 515, 637 with minimal modification.

Problem 4: Lowest Common Ancestor of a Binary Tree

Link: LeetCode 236

Quick Summary: Given a binary tree and two nodes p and q, find their lowest common ancestor (deepest node that has both p and q as descendants, where a node is a descendant of itself).

Industry Context: Git’s merge-base algorithm (finding the common ancestor commit in a DAG) is a generalization of LCA. In microservice dependency graphs, LCA identifies the deepest shared service owner for an ownership/escalation policy. In RDBMS query optimizers, LCA of two plan nodes determines where a join or filter can be pushed down.

Approach 1: BFS parent map (explicit ancestry)

// Time: O(n)  Space: O(n) parent map + O(h) ancestor set
public TreeNode lcaWithParentMap(TreeNode root, TreeNode p, TreeNode q) {
    Map<TreeNode, TreeNode> parent = new HashMap<>();
    Queue<TreeNode> queue = new LinkedList<>();
    parent.put(root, null);
    queue.offer(root);
    // BFS until both p and q are recorded
    while (!parent.containsKey(p) || !parent.containsKey(q)) {
        TreeNode node = queue.poll();
        if (node.left  != null) { parent.put(node.left,  node); queue.offer(node.left); }
        if (node.right != null) { parent.put(node.right, node); queue.offer(node.right); }
    }
    // Collect p's ancestors
    Set<TreeNode> ancestors = new HashSet<>();
    for (TreeNode cur = p; cur != null; cur = parent.get(cur)) ancestors.add(cur);
    // Walk q upward until hitting p's ancestor set
    for (TreeNode cur = q; ; cur = parent.get(cur)) {
        if (ancestors.contains(cur)) return cur;
    }
}
  • Time: O(n)
  • Space: O(n) — parent map stores every node
  • Tradeoff: More space, but makes the parent relationship tangible. Good when you need to support multiple LCA queries on the same tree (build the map once, answer many queries).

Approach 2: Recursive DFS (optimal — O(1) auxiliary space)

// Time: O(n)  Space: O(h) recursion stack only
public TreeNode lcaRecursive(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode leftResult  = lcaRecursive(root.left,  p, q);
    TreeNode rightResult = lcaRecursive(root.right, p, q);
    // Both subtrees returned non-null → p and q in different subtrees
    if (leftResult != null && rightResult != null) return root;
    // One subtree has both (or one of them) — propagate
    return leftResult != null ? leftResult : rightResult;
}
  • Time: O(n)
  • Space: O(h)
  • Key Insight: The function serves double duty — it returns a node reference that bubbles up as a “signal”:
    • If it finds p or q, it returns that node to the parent frame.
    • If both children return non-null, the current node is the split point → LCA.
    • If only one child returns non-null, it means both targets are in that subtree, or the non-null node IS the LCA (one target is ancestor of the other).
      The cleverness is that this single-pass postorder DFS encodes a three-valued result (found p, found q, found LCA) through a single return type.

Problem 5: Binary Tree Maximum Path Sum

Link: LeetCode 124

Quick Summary: A path in a binary tree is any sequence of nodes where each pair is connected, with no node repeated. Return the maximum sum of any such path (can start and end at any node).

Industry Context: Distributed query planners (Presto/Trino) optimize sub-plan trees to maximize data locality — this is structurally equivalent to finding the highest-value connected subgraph in a plan tree. Also: network topology optimization (finding the highest-bandwidth path segment in a hierarchical network), and financial rollup trees (finding the highest-revenue segment across a product hierarchy).

Approach 1: Brute Force — per-node path scan

// Time: O(n²)  Space: O(h²) — recomputes gains for every node
public int maxPathSumBrute(TreeNode root) {
    if (root == null) return Integer.MIN_VALUE;
    int throughRoot = root.val
        + Math.max(0, gainFrom(root.left))
        + Math.max(0, gainFrom(root.right));
    int leftBest  = maxPathSumBrute(root.left);
    int rightBest = maxPathSumBrute(root.right);
    return Math.max(throughRoot, Math.max(leftBest, rightBest));
}
 
private int gainFrom(TreeNode node) {
    if (node == null) return 0;
    int left  = Math.max(0, gainFrom(node.left));
    int right = Math.max(0, gainFrom(node.right));
    return node.val + Math.max(left, right);   // single arm only
}
  • Time: O(n²) — gainFrom called O(n) times, each takes O(n)
  • Space: O(h) per call frame
  • Tradeoff: Correct but impractical. Same sub-problems recomputed repeatedly — classic signal to apply memoization or restructure as a single-pass DFS.

Approach 2: Single-pass postorder DFS with global max (optimal)

// Time: O(n)  Space: O(h)
private int globalMax;
 
public int maxPathSum(TreeNode root) {
    globalMax = Integer.MIN_VALUE;
    bestArm(root);
    return globalMax;
}
 
// Returns the best "arm" extending from this node upward (cannot bend)
private int bestArm(TreeNode node) {
    if (node == null) return 0;
    int leftArm  = Math.max(0, bestArm(node.left));   // clamp negatives
    int rightArm = Math.max(0, bestArm(node.right));
    // This node as the apex — can take both arms (path bends here)
    globalMax = Math.max(globalMax, node.val + leftArm + rightArm);
    // Report to parent: only one arm (path cannot bend again above this node)
    return node.val + Math.max(leftArm, rightArm);
}
  • Time: O(n)
  • Space: O(h)
  • Key Insight: The core tension is between two roles at each node:
    1. Local evaluation (path apex): node.val + leftArm + rightArm — the path bends here and can use both branches. This is a candidate answer, updated to globalMax.
    2. Upward contribution (arm to parent): node.val + max(leftArm, rightArm) — the path must remain a straight line from this node upward; it can only pick one branch.
      Clamping arm values to 0 (Math.max(0, ...)) elegantly handles negative subtrees: it’s always better to exclude them (treat them as 0-length extensions).
      This “report up vs. update global” pattern recurs in LC 543 (Diameter), LC 687 (Longest Univalue Path), and many tree-global-aggregation problems.

DFS vs BFS Decision Guide

When to Prefer DFS

  • Path problems: root-to-leaf paths, path sum, path existence — the recursion call stack naturally maintains the current path.
  • Depth-first exploration: checking existence of a value, validating BST property, tree serialization.
  • Bottom-up aggregation: any problem where a parent’s answer depends on combining children’s answers (height, diameter, max path sum, LCA). Postorder DFS is the natural fit.
  • Space advantage for tall, narrow trees: DFS uses O(h) space; BFS uses O(w). For a balanced tree h ≈ log n but for a bushy tree w ≈ n/2.
  • When recursion stack matches problem semantics: e.g., “path from root to this node” is implicitly tracked in the call stack.

When to Prefer BFS

  • Level-order output required: LC 102, 107, 199, 637.
  • Shortest path / nearest neighbor: BFS finds the shallowest occurrence first. Use for “minimum depth”, “closest leaf”, “shortest path in unweighted graph”.
  • Level-by-level processing: when each level must be fully processed before the next (wave propagation, barrier synchronization).
  • Space advantage for deep, narrow trees: BFS uses O(w); if the tree is a long chain (degenerate), w=1 but h=n, so BFS wins.
  • Avoiding recursion stack overflow: iterative BFS is always safe; deep recursive DFS can blow the JVM stack (default ~500-1000 frames for complex trees).

Complexity Comparison Table

MetricRecursive DFSIterative DFS (explicit stack)BFS (queue)
TimeO(n)O(n)O(n)
Space (balanced tree)O(log n)O(log n)O(n/2) = O(n)
Space (skewed tree)O(n)O(n)O(1)
Space (perfect tree)O(log n)O(log n)O(n/2)
Stack overflow riskYes (deep trees)NoNo
Level isolationNo (extra bookkeeping)NoYes (natural)
Path trackingYes (call stack = path)Yes (explicit stack)No (needs parent map)
Interview clarityHighMediumHigh for level problems

Key Takeaways

Pattern Recognition Triggers

  • “Maximum/minimum depth” or “height” → postorder recursive DFS; 1 + max(left, right)
  • “Level order” or “by level” or “zigzag” → BFS with levelSize = queue.size() snapshot
  • “Lowest common ancestor” → postorder DFS; return the node that “carries the signal” up
  • “Path sum” or “maximum path” → postorder DFS with two distinct computations: arm-to-parent vs. path-through-node (bend point)
  • “Invert / mirror / flip” → either traversal order works; swap children at each node
  • “Closest node” or “fewest hops” → BFS, not DFS
  • Parent relationship needed across multiple queries → build a parent HashMap via BFS once

Common Tree Pitfalls

  • Null checks first: every recursive method’s base case must handle null before accessing .left, .right, or .val. Forgetting this causes NPEs on empty subtrees or leaf children.
  • Off-by-one on depth: depth of a single-node tree is 1 (or 0 if counting edges). Clarify with interviewer upfront; LeetCode 104 uses node-count (so a single node = depth 1).
  • Negative values in path problems: never assume node values are non-negative (LC 124 explicitly has negatives). Always clamp arm values with Math.max(0, arm).
  • Integer overflow in path sum: max sum can exceed Integer.MAX_VALUE with large trees; consider long if node values and tree size are large.
  • LCA prerequisite: LC 236 assumes both p and q are guaranteed to exist in the tree. Without that guarantee, you need a boolean return or separate existence check — state this assumption explicitly.
  • globalMax initialization: initialize to Integer.MIN_VALUE, not 0 — otherwise all-negative trees return 0 instead of the correct (least negative) answer.
  • BFS queue null pollution: do not enqueue null children; always guard with if (child != null) before queue.offer(child). TreeNode.print() enqueues nulls for visualization — don’t copy that pattern in algorithm code.

System Design Connections

  • Tree DFS → Recursive descent parsers: JSON/XML/SQL parsers are DFS postorder evaluators — leaf tokens evaluated first, parent expressions computed from children. Same pattern as max path sum.
  • BFS → Distributed gossip protocols: epidemic-style broadcast propagates level by level. BFS models the “infection front” — nodes at level k are those reached in exactly k hops.
  • LCA → Version control (git merge-base): finding the common ancestor of two commits in a DAG is LCA. Git uses a BFS/Dijkstra hybrid for weighted DAGs (commit timestamps).
  • Level-order serialization → Distributed tree replication: Kafka/ZooKeeper serialize tree state (config trees, watch trees) in BFS order so receivers can reconstruct parent-child links with an index formula: parent of node at index i is at (i-1)/2.
  • Postorder aggregation → MapReduce/Spark DAG execution: physical plan trees are executed postorder — leaf stages (data sources) execute first, root stage (final aggregation) last. Cost model computation is also postorder DFS.
  • Max path sum pattern → Network diameter: the diameter of a tree (longest path between any two nodes) uses the identical arm + arm at each node technique — just without negative clamping (LC 543 is the diameter variant).

Graph View

Backlinks