Trees
Traversal choice, bottom-up vs top-down recursion, LCA and tree DP.
9 notes · 46 min total
Questions0 of 59 done
Warm up with these before Phase 1.
Patterns
- 1Pick the Traversal: DFS Orders and BFS LevelsWhen to reach for preorder, inorder, postorder or level-order BFS, and the BFS tricks for width, completeness and next pointers.6 min
- 2Bottom-Up Return Values (the Manager)Let children report up to the parent, and separate what you compute at a node from what you return to its parent.5 min
- 3Top-Down State and Path Prefix Sums (the Traveler)Carry history down the tree as arguments, and count downward paths with a prefix-sum map that you undo on the way back up.5 min
- 4LCA and Parent PointersFind the lowest common ancestor by bubbling status up, and add parent pointers when you need to walk up the tree.6 min
- 5Build a Tree from TraversalsRebuild a binary tree from two traversal orders: find the root, split the rest, and avoid the hidden O(n²) of index() and slicing.4 min
- 6BST OperationsSearch, insert and delete in a binary search tree by pruning with the ordering, and re-attach subtrees on the way back up.5 min
- 7Serialize and Fingerprint SubtreesTurn a tree into a string and back with null markers, and give each subtree an integer ID to find duplicates in O(n).5 min
- 8Tree DP with StatesReturn a small tuple of states from each subtree, combine them in postorder, and read the answer off the root.6 min
- 9Rewiring and PruningChange a tree's shape in place: delete nodes in postorder so parents can re-check themselves, and splice subtrees by returning their ends.4 min