LeetCode 226 – Invert Binary Tree
Swap every node’s left/right.
Recursively or iteratively swap left ↔ right for each node.
DFS (pre/post) or BFS works.
Time O(n), Space O(h) (recursion) or O(w) (queue).
Tags: Tree, DFS/BFS.
LeetCode 104 – Maximum Depth
Return height of tree.
Depth = 1 + max(depth(left), depth(right)).
Or BFS level count.
O(n) time, O(h) space.
Tags: Recursion, BFS.
LeetCode 543 – Diameter
Longest path between any two nodes (#edges).
DFS returns height; update global best = max(best, leftH + rightH).
Answer is best.
O(n) time, O(h) space.
Tags: DFS, Height.
LeetCode 110 – Balanced?
|height(L) − height(R)| ≤ 1 for all nodes.
Postorder: get heights; if any subtree unbalanced, bubble up sentinel (e.g., -1).
O(n) time, O(h) space.
Tags: DFS, Pruning.
LeetCode 572 – Subtree of Another Tree
Is t a subtree of s?
Traverse s; when node value == root(t), run isSameTree.
Short-circuit on match.
O(n·m) worst; average faster with pruning or hashes.
Tags: DFS, Matching.
LeetCode 235 – LCA in BST
Find LCA(p, q).
Use BST order:
If both < root → go left; both > root → right; else root is LCA.
Iterative or recursive.
O(h) time, O(1)/O(h) space.
Tags: BST properties.
LeetCode 102 – Level Order
Nodes by level (left→right).
BFS queue; process current level size, push children.
Collect list per level.
O(n) time, O(w) space.
Tags: BFS.
LeetCode 199 – Right Side View
One node per level as seen from right.
BFS: record the last node popped per level.
Or DFS right-first, keep first visit at each depth.
O(n) time, O(w)/O(h) space.
Tags: BFS/DFS.
LeetCode 100 – Same Tree
Structural + value equality?
Recursively compare: both null → true; one null → false; vals equal & left/same & right/same.
O(n) time, O(h) space.
Tags: DFS.
LeetCode 1448 – Count Good Nodes
Node is “good” if ≥ max on path root→node.
DFS carry maxSoFar; count if val ≥ maxSoFar.
Update maxSoFar = max(maxSoFar, val).
O(n) time, O(h) space.
Tags: DFS with state.
LeetCode 98 – Validate BST
Is tree strictly BST?
Method 1: DFS with (low, high) bounds; node.val must be (low, high).
Method 2: Inorder traversal must be strictly increasing.
O(n) time, O(h) space.
Tags: BST, Inorder, Bounds.
LeetCode 230 – Kth Smallest in BST
Inorder traversal yields sorted order; decrement k until 0.
Iterative stack to avoid recursion.
(Follow-ups: maintain subtree sizes for updates.)
O(h + k) time, O(h) space.
Tags: BST, Inorder.
LeetCode 105 – Build Tree (Preorder + Inorder)
Preorder gives root order; inorder splits left/right.
Map val → inorderIndex for O(1) splits.
Recurse with index ranges; advance preorder pointer.
O(n) time, O(n) space.
Tags: Recursion, Array indices.
LeetCode 124 – Max Path Sum
Path can start/end anywhere; at most one turn at a node.
DFS returns max gain to parent: max(0, max(leftGain, rightGain)) + val.
Update global: best = max(best, leftGain + rightGain + val).
Handle negatives.
O(n) time, O(h) space.
Tags: DP on Trees.
LeetCode 297 – Serialize/Deserialize
Convert between tree and string.
Common: BFS with null markers (e.g., #) and commas.
Serialize: level order append;
Deserialize: rebuild by reading queue and attaching children.
Alternatively: Preorder with sentinel + index.
O(n) time, O(n) space.
Tags: BFS/Preorder, Encoding.
