LC Patterns — Trees & BSTs

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

1. Null is the base case — handle it first. if (!node) return ⟨identity⟩; opens almost every recursive tree function; the identity (0, true, INT_MIN, nullptr) is a design decision, not boilerplate.
2. Nodes vs edges: "depth/diameter in nodes" vs "in edges" differ by one; LC 543 counts edges, 104 counts nodes. Decide the unit before coding and write it in a comment (the fencepost bug of this topic).
3. Return value ≠ global answer: in diameter/max-path problems, f(node) returns the best downward arm while the answer (the best arch through any node) updates a captured variable. Mixing them is the #1 hard-tree bug.
4. BST validation needs ranges, not parent-child checks: comparing each node only to its parent wrongly accepts invalid trees (a right-grandchild smaller than the grandparent). Pass (lo, hi) bounds down. And use long long bounds — test values include INT_MIN/INT_MAX.
5. BFS level loops must snapshot the queue size: int sz = q.size(); for (int i = 0; i < sz; ++i) — reading q.size() live while pushing children merges levels together.
6. Recursion depth: a skewed tree of 10⁴ nodes can overflow the stack — mention the iterative/explicit-stack conversion (and know Morris traversal by name for the O(1)-space follow-up; implement only if asked).
7. Smart pointers/new in interviews: raw pointers are fine and expected for LC-style tree code; say so and move on.

What it is: Compute a property of every subtree from its children's answers: height = 1 + max(child heights); a tree is balanced when both subtrees are balanced and their heights differ by ≤ 1. One post-order pass, O(n).

Intuition: Post-order (children before self) is the order for bottom-up: by the time you reach a node, its children's answers already exist. The efficiency idiom: fold the check into the height computation — a naive "isBalanced calls height at every node" is O(n²); returning height and balance together (a sentinel -1 = "unbalanced somewhere below") makes it O(n). Combining several return values into one pass is the skill this pattern drills.

Approach:

int check(TreeNode* n) {                    // returns height, or -1 if unbalanced below
    if (!n) return 0;
    int l = check(n->left);  if (l == -1) return -1;
    int r = check(n->right); if (r == -1) return -1;
    if (abs(l - r) > 1) return -1;
    return 1 + max(l, r);
}
bool isBalanced(TreeNode* root) { return check(root) != -1; }

What it is: Carry state down from the root as parameters — the remaining target sum, the number built so far, the max value seen on this path — and evaluate at leaves (or at every node). "Does a root-to-leaf path sum to k?", "sum all root-to-leaf numbers," "count nodes ≥ every ancestor."

Intuition: Path-from-root state is exactly what call parameters model: each recursive call is one step along a path, and the call stack is the path. No data structure needed — the recursion shape mirrors the problem shape. Evaluate-at-leaf problems must define "leaf" precisely (!left && !right), not "null child" — checking at null double-counts through one-child nodes.

Approach:

int dfs(TreeNode* n, int cur) {             // 129: cur = number formed root..parent
    if (!n) return 0;
    cur = cur * 10 + n->val;
    if (!n->left && !n->right) return cur;  // true leaf: contribute the path's number
    return dfs(n->left, cur) + dfs(n->right, cur);
}

What it is: Recurse on two nodes in lockstep: same-tree (equal here && left-left equal && right-right equal), symmetric (mirror: compare left-with-right and right-with-left), subtree-of (a same-tree check launched at every node), merge (combine two trees node-wise).

Intuition: The contract just takes two nodes: f(a, b). Null-handling does most of the work — both null = true/nullptr, one null = false/the-other. Symmetry's one insight: a tree is symmetric when its left subtree mirrors its right, and "mirrors" swaps children in the comparison (mirror(a->left, b->right) && mirror(a->right, b->left)).

Approach:

bool same(TreeNode* a, TreeNode* b) {
    if (!a || !b) return a == b;            // both null → true; one null → false
    return a->val == b->val && same(a->left, b->left) && same(a->right, b->right);
}

What it is: Rebuild or rewire the tree itself: swap every node's children (invert), overlay two trees (merge), rewrite the tree into a linked list in preorder (flatten). The recursion returns the new subtree root, and the parent stitches it in.

Intuition: Treat "transform this tree" as "transform the children, then fix up this node" — post-order rewiring. The contract sentence matters doubly here because you're mutating: f(node) returns the root of the transformed subtree. Flatten's trick: recurse right first, thread each node's rewired left list between itself and its already-flattened right — or the O(1)-space version: for each node with a left child, splice the left subtree's rightmost node onto the right child.

Approach:

TreeNode* invertTree(TreeNode* root) {
    if (!root) return nullptr;
    TreeNode* l = invertTree(root->left);
    root->left = invertTree(root->right);
    root->right = l;
    return root;
}

What it is: Rebuild a unique binary tree from two traversal orders (preorder + inorder, or inorder + postorder), or build a balanced BST from a sorted array. The recurring shape: one traversal names the root, the other (inorder) splits the left subtree from the right.

Intuition: Preorder's first element is the root; find it in inorder — everything to its left is the left subtree, everything to its right is the right subtree; recurse on the matching slices. Sorted-array→BST is the same idea with the middle element as the root (balance for free). Fact to state: preorder + postorder alone is ambiguous (one-child nodes) — inorder is the disambiguator.

Approach:

unordered_map<int,int> pos;                  // inorder value → index (build once: O(1) splits)
TreeNode* build(vector<int>& pre, int& pi, int lo, int hi) {
    if (lo > hi) return nullptr;
    TreeNode* root = new TreeNode(pre[pi++]);
    int mid = pos[root->val];
    root->left  = build(pre, pi, lo, mid - 1);   // preorder consumes left-first —
    root->right = build(pre, pi, mid + 1, hi);   // order of these two calls is load-bearing
    return root;
}

What it is: Process the tree level by level with a queue: collect levels, take each level's last node (right-side view), alternate direction (zigzag), connect next pointers within a level. Also the right tool whenever the ask is "nearest/shallowest" — BFS finds the minimum depth before DFS finishes exploring.

Intuition: The queue-size snapshot (§0.5) turns a plain BFS into a level-aware one: everything in the queue at the loop's start is exactly one level. Every level-order variant is that loop plus a different per-level action (record all / record last / reverse alternate levels / wire next pointers). Right-side view = each level's final node — a one-line change, not a new algorithm.

Approach:

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> out;
    if (!root) return out;
    queue<TreeNode*> q; q.push(root);
    while (!q.empty()) {
        int sz = q.size(); out.emplace_back();
        for (int i = 0; i < sz; ++i) {
            TreeNode* n = q.front(); q.pop();
            out.back().push_back(n->val);
            if (n->left) q.push(n->left);
            if (n->right) q.push(n->right);
        }
    }
    return out;
}

What it is: Find the deepest node that has both targets in its subtree. General tree: post-order — if the searches of the left and right subtrees each found one target, this node is the LCA. BST: no recursion insight needed — prune by value: both targets smaller → go left; both bigger → go right; they split (or one equals the node) → found.

Intuition: The general-tree recursion returns "the target found in this subtree, or the LCA if both were found": null+null = null, one-sided = pass it up, both sides non-null = I'm the split point. It works because the first node where the targets diverge is, by definition, their lowest common ancestor. The BST version is the pruning superpower: the LCA is the first node whose value falls between the targets on the root-down walk — O(h), no recursion required.

Approach:

TreeNode* lca(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* l = lca(root->left, p, q);
    TreeNode* r = lca(root->right, p, q);
    if (l && r) return root;                 // targets split here → this is the LCA
    return l ? l : r;
}

What it is: Everything that exploits "inorder = sorted": validate a BST (the inorder sequence must be strictly increasing — or pass ranges down), k-th smallest (inorder, stop at the k-th visit), BST iterator (a paused inorder traversal: a stack of left-spines; next() pops and then pushes the popped node's right spine).

Intuition: The two interchangeable tools: range-passing (each node constrains its subtrees to (lo, hi) — top-down, Pattern 2 for BSTs) and inorder-walking (mentally flatten to sorted order and apply array thinking — k-th, prev/next, two-sum-in-BST). The iterator teaches the deeper skill: turning a recursion into an explicit stack you can pause — the left spine in the stack is exactly the recursion's pending frames, giving O(h) memory and O(1) amortized next().

Approach:

bool validate(TreeNode* n, long long lo, long long hi) {
    if (!n) return true;
    if (n->val <= lo || n->val >= hi) return false;
    return validate(n->left, lo, n->val) && validate(n->right, n->val, hi);
}
// call: validate(root, LLONG_MIN, LLONG_MAX)

What it is: The hard-tree archetype: max path sum (any node to any node), longest univalue path, house-robber-on-a-tree. At each node, the value you return to the parent (best single downward arm — the parent can only extend one arm) differs from the value you record globally (best arch joining both arms through this node).

Intuition: A path through a tree has a unique highest node — its apex. Enumerate paths by their apex: at each node, the best path apexed here = node + best-left-arm + best-right-arm; record it globally. But a parent extending through this node can use only ONE arm (paths can't fork) — so return node + max(arm). Clamp negative arms to 0 ("don't take a bad arm"). House Robber III is the same discipline with a pair return: (best if this node robbed, best if not).

Approach:

int best = INT_MIN;
int arm(TreeNode* n) {                       // best downward path STARTING at n (≥ its value)
    if (!n) return 0;
    int l = max(arm(n->left), 0);            // negative arm → drop it
    int r = max(arm(n->right), 0);
    best = max(best, n->val + l + r);        // arch apexed at n → record globally
    return n->val + max(l, r);               // parent may extend only one arm → return
}

What it is: Structural edits that keep the BST rule intact. Insert: walk down by comparison, attach at the null spot. Delete: the three-case classic — leaf (drop it), one child (splice the child up), two children (replace the value with the inorder successor — the leftmost node of the right subtree — then delete that node, which is guaranteed to be case 1 or 2). Trim: recursively discard subtrees wholly outside [lo, hi].

Intuition: All three are "recurse toward the target by comparison, and return the (possibly new) subtree root so the parent re-links" — the returning-root contract from Pattern 4 under the BST pruning from Pattern 8. Delete's two-child case works because the inorder successor is the smallest value greater than the node — promoting it keeps everything on the left smaller and everything on the right bigger. Trim's power move: if node->val < lo, then the entire left subtree is also < lo — return the trimmed right subtree and skip half the tree.

Approach:

TreeNode* deleteNode(TreeNode* root, int key) {
    if (!root) return nullptr;
    if (key < root->val)      root->left  = deleteNode(root->left, key);
    else if (key > root->val) root->right = deleteNode(root->right, key);
    else {
        if (!root->left)  return root->right;      // cases 1 & 2: splice
        if (!root->right) return root->left;
        TreeNode* s = root->right;                  // case 3: inorder successor
        while (s->left) s = s->left;
        root->val = s->val;
        root->right = deleteNode(root->right, s->val);  // delete successor (easy case)
    }
    return root;
}

What it is: Encode a tree to a string and rebuild it exactly (297), or use serialization as a canonical key to find duplicate subtrees (652) — hash each subtree's serialization; same key = identical subtree. The tree-world version of the arrays-strings canonical-key pattern.

Intuition: Preorder with explicit null markers uniquely determines a binary tree — the nulls carry the structure that made preorder-alone ambiguous in Pattern 5. Deserialization is then one left-to-right pass with the same shared-cursor trick: read a token; if it's the null-marker return; else make the node and recurse left, then right. For duplicate detection, build keys bottom-up (val + "," + leftKey + "," + rightKey) so each subtree's key is O(1) to assemble from its children — and intern keys to ints (unordered_map<string,int>) to avoid O(n²) string growth on deep trees.

Approach:

void ser(TreeNode* n, string& out) {
    if (!n) { out += "#,"; return; }
    out += to_string(n->val) + ",";
    ser(n->left, out); ser(n->right, out);
}
TreeNode* deser(istringstream& in) {
    string tok; getline(in, tok, ',');
    if (tok == "#") return nullptr;
    TreeNode* n = new TreeNode(stoi(tok));
    n->left = deser(in); n->right = deser(in);   // same order as serialization — load-bearing
    return n;
}