Binary Trees & BST: Deriving the Optimal Solution for 5 Problems (LC 104/102/236/98/230)

Tree problems look endlessly varied, but they boil down to two through-lines: ① pick the right traversal (DFS or BFS), and ② is it a BST — can you exploit "left < root < right"? Nail those two and most tree problems are just template-filling.

This post strings the two through-lines across 5 problems, continuing the full derivation flow:

📋 Problem → 🧭 break down → brute force → bottleneck → insight → optimum → code

• DFS recursion for depth (104) → BFS by level (102) → LCA via subtree return values (236) → validating a BST with bounds (98) → the kth smallest via BST's in-order order (230)

🌲 Setup: all use the standard node. Python: node.val / node.left / node.right; C++: TreeNode { int val; TreeNode *left, *right; }.

① LC 104 — Maximum Depth of Binary Tree

📋 Problem: Given the root of a binary tree, return its maximum depth (the number of nodes along the longest path from root to the farthest leaf).

Example: root = [3,9,20,null,null,15,7] → 3

🧭 From reading the problem to the solution

1. Break it down: a tree's depth = 1 (the root) + the deeper of its two subtrees. A natural recursive definition.
2. First instinct: straight recursion, base case = empty node returns 0.
3. Key insight: this is the cleanest DFS (post-order) — compute both subtree depths, then combine.
4. Optimum: three lines of recursion.

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

int maxDepth(TreeNode* root) {
    if (!root) return 0;
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}

• Complexity: O(n) time (each node once), O(h) space (recursion stack, h = height; worst O(n)).
• Pitfall: depth counts nodes, not edges; empty tree returns 0. A heavily skewed (chain-like) tree gives recursion depth O(n) and may overflow the stack — switch to BFS if needed.

② LC 102 — Binary Tree Level Order Traversal

📋 Problem: Given the root of a binary tree, return its node values level by level, left to right (one array per level).

Example: root = [3,9,20,null,null,15,7] → [[3],[9,20],[15,7]]

🧭 From reading the problem to the solution

1. Break it down: "level by level" — exactly what DFS is bad at (it dives deep). We want breadth-first.
2. Brute force: compute the height, then scan each level separately, O(n·h). Wasteful.
3. Key insight (BFS): use a queue and, at the start of each round, freeze the current queue size sz — those sz nodes are one level; pop and collect them all, pushing their children for the next level.
4. Optimum: split levels by len(queue) inside the loop.

from collections import deque

def levelOrder(root):
    if not root:
        return []
    res, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):       # freeze this level's size
            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

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if (!root) return res;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int sz = q.size();            // freeze this level's size
        vector<int> level;
        for (int i = 0; i < sz; i++) {
            TreeNode* node = q.front(); q.pop();
            level.push_back(node->val);
            if (node->left)  q.push(node->left);
            if (node->right) q.push(node->right);
        }
        res.push_back(level);
    }
    return res;
}

• Complexity: O(n) time, O(n) space (widest level).
• Pitfall: freeze sz = len(q) before the loop — you push the next level inside it, so a dynamic length check would mix levels. This is the crux of leveled BFS.

③ LC 236 — Lowest Common Ancestor of a Binary Tree

📋 Problem: Given a binary tree and two nodes p, q, return their lowest common ancestor (LCA). Note: a plain binary tree, not a BST.

Example: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 → 3; p = 5, q = 4 → 5 (a node can be its own ancestor)

🧭 From reading the problem to the solution

1. Break it down: the LCA is the deepest node that can reach both p and q in its subtrees (or is one of them).
2. Brute force: find root-to-p and root-to-q paths, then the last common node — O(n) but stores two paths.
3. Key insight (post-order + subtree return values): ask each node "does my subtree contain p or q?" Recursion returns that node if found, else null. If a node's left and right each return non-null (p on one side, q on the other), it's the LCA; if only one side has them, bubble that up.
4. Optimum: one post-order DFS, no stored paths.

def lowestCommonAncestor(root, p, q):
    if not root or root == p or root == q:
        return root
    left  = lowestCommonAncestor(root.left,  p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left and right:          # p and q split across sides → here is LCA
        return root
    return left or right        # both on one side → bubble it up

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* left  = lowestCommonAncestor(root->left,  p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (left && right) return root;     // split → LCA
    return left ? left : right;         // one side → bubble up
}

• Complexity: O(n) time, O(h) space.
• Pitfall: ① the base case includes root == p or root == q — a node can be its own ancestor; ② you can't use BST value comparison here (it's a plain tree) — rely on subtree return values. Contrast LC 235 (BST LCA), where you can compare values directly.

④ LC 98 — Validate Binary Search Tree

📋 Problem: Given a binary tree, decide if it's a valid BST: every node's left subtree has all values less than it, and the right subtree all greater.

Example: root = [2,1,3] → true; root = [5,1,4,null,null,3,6] → false (4 is in 5's right subtree but < 5)

🧭 From reading the problem to the solution

1. Break it down: the BST condition is about the whole subtree's range, not just immediate children.
2. The wrong instinct: check only left.val < node.val < right.val. Counterexample: in [5,1,4,null,null,3,6], 4 is 5's right-grandchild; locally 3<4<6 is fine, but 4 < 5 violates the global BST — local comparison misses it.
3. Key insight (recurse with bounds): as you descend, tighten an allowed open interval (low, high): going left sets the upper bound to node.val, going right sets the lower bound to node.val. Each node must fit its own interval.
4. Optimum: DFS carrying (low, high), starting at (-∞, +∞).

def isValidBST(root):
    def valid(node, low, high):
        if not node:
            return True
        if not (low < node.val < high):     # must fit the open interval
            return False
        return (valid(node.left,  low, node.val) and
                valid(node.right, node.val, high))
    return valid(root, float('-inf'), float('inf'))

bool valid(TreeNode* node, long low, long high) {
    if (!node) return true;
    if (!((long)node->val > low && (long)node->val < high)) return false;
    return valid(node->left, low, node->val) &&
           valid(node->right, node->val, high);
}
bool isValidBST(TreeNode* root) {
    return valid(root, LONG_MIN, LONG_MAX);
}

• Complexity: O(n) time, O(h) space.
• Pitfall: ① don't compare only immediate children — pass bounds down; ② node values can equal INT_MIN/INT_MAX, so use long bounds in C++ (or ±inf in Python) to avoid overflow; ③ a BST disallows duplicates — use strict inequalities. Alternative: an in-order traversal should be strictly increasing — compare against the previous value as you go.

⑤ LC 230 — Kth Smallest Element in a BST

📋 Problem: Given a BST and integer k, return the kth smallest element (1-indexed).

Example: root = [3,1,4,null,2], k = 1 → 1; root = [5,3,6,2,4,null,null,1], k = 3 → 3

🧭 From reading the problem to the solution

1. Break it down: "kth smallest" — if you can get the values sorted ascending, the kth one is the answer.
2. Brute force: extract all values and sort, O(n log n) — but ignores the BST.
3. Key insight (BST in-order = ascending): a BST's in-order traversal (left → root → right) is exactly ascending. So traverse in-order and return the kth visited node — no need to finish the tree.
4. Optimum: iterative in-order (explicit stack), counting as you go, returning the moment you hit k.

def kthSmallest(root, k):
    stack, node = [], root
    while stack or node:
        while node:                  # go as left as possible
            stack.append(node)
            node = node.left
        node = stack.pop()           # visit in ascending order
        k -= 1
        if k == 0:
            return node.val
        node = node.right            # then the right subtree

int kthSmallest(TreeNode* root, int k) {
    stack<TreeNode*> st;
    TreeNode* node = root;
    while (!st.empty() || node) {
        while (node) { st.push(node); node = node->left; }   // leftmost
        node = st.top(); st.pop();                            // visit
        if (--k == 0) return node->val;
        node = node->right;                                   // go right
    }
    return -1;
}

• Complexity: O(h + k) time (only to the kth), O(h) space.
• Pitfall: ① the key is "in-order = ascending," a BST-only property; ② iterative in-order lets you stop early (at k), cheaper than collecting everything; ③ follow-up: if the BST is frequently modified and kth-smallest is queried often, maintain a "left-subtree node count" per node to drop each query to O(h).

One Table to Remember It All

Pattern-Recognition Cheats

• "depth / height / path sum / invert" → DFS recursion; think "what does each subtree return, and how do I combine them?"
• "level by level / each level / rightmost node / zigzag" → BFS; remember to freeze sz.
• "LCA / relationship between two nodes" → post-order DFS with subtree return values; if it's a BST, compare values directly (235).
• "validate BST" → recurse with bounds, or check in-order is strictly increasing.
• "BST + kth smallest / sorted / range query" → in-order traversal (ascending), with early exit.

The essence of tree problems is two questions: "DFS or BFS for this?" and "Is it a BST — can I use left < root < right?" Answer those two and the code almost writes itself.