Trees Pattern Hub

TC: O(N) · SC: O(W)

Standard FIFO BFS queue: snapshot `qLen = len(q)` at the start of every outer loop iteration so the inner loop consumes strictly one depth level.

Binary Tree Maximum Path Sum

hard

Post-order DFS computes the maximum downward *single-branch* gain (`max(0, dfs(child))` — clamp negatives to `0`). At each node `u`, evaluate splitting through `u` (`u.val + leftGain + rightGain`) against the global max, then return `u.val + max(leftGain, rightGain)` upward.

Diameter of Binary Tree

In a single bottom-up DFS returning height, any node `u` can serve as the highest turning point of a path of edge length `leftH + rightH`. Maintain `best = max(best, leftH + rightH)` globally while returning `1 + max(leftH, rightH)` upward.

Invert Binary Tree

At every node, swap `left` and `right` children, then recursively invert both subtrees (pre-order, post-order, or BFS queue all preserve the mirror invariant).

Kth Smallest Element in a BST

TC: O(H + k) · SC: O(H)

Iterative inorder traversal using an explicit stack stops immediately on the `k`-th pop—visiting only `O(H + k)` nodes instead of traversing the entire tree.

Lowest Common Ancestor of a Binary Search Tree

TC: O(H) · SC: O(1)

Walk down from `root` iteratively using the BST ordering property: if both `p.val` and `q.val` are strictly less than `curr.val`, go left; if both strictly greater, go right; otherwise `curr` is the split point (LCA).

Maximum Depth of Binary Tree

Post-order recurrence: an empty tree has depth `0`; otherwise `1 + max(maxDepth(left), maxDepth(right))`.

Same Tree

TC: O(min(P, Q)) · SC: O(min(Hp, Hq))

Base cases first: both null => `True`; one null => `False`; values differ => `False`. Otherwise recursively verify left and right child equality.

Subtree of Another Tree

TC: O(S * T) · SC: O(Hs)

A tree rooted at `root` contains `subRoot` iff `sameTree(root, subRoot)` or `subRoot` is in `root.left` or `root.right`. (For huge trees, serialize preorder with null sentinels + `#` delimiter and run KMP in `O(S + T)`.)

Validate Binary Search Tree