Algorithms from zero
Trees: build a BST toolkit
You have walked trees, ordered them, and run tree DP on paper. Now build the toolkit yourself: a binary search tree that inserts, searches, traverses four ways, validates its own invariant, and reports its diameter and balance. The tests are where the unit’s edge cases — degenerate trees, ancestor bounds, leaf heights — stop being trivia and start being code that either passes or fails.
Turn the unit’s mental model into a working, tested data-structure library: implement BST insert and search, all four traversals, a correct (range-bound) BST validator, and the tree-DP metrics height, diameter, and balance — then prove each with tests, including the degenerate case that breaks O(log n).
Implement a self-contained binary search tree library in the language of your choice, exposing insert, search, the four traversals, a correct BST validator, and tree-DP metrics — backed by a test suite that demonstrates both the happy path and the degenerate worst case.
- All traversals return the correct sequence on a hand-drawn example tree, verified against your own pen-and-paper trace.
- isValidBST returns false for the deliberately-invalid tree and true for every valid BST built by insert — the test for the local-check bug passes.
- height, diameter, and isBalanced match hand-computed values on at least two trees, one balanced and one skewed.
- The sorted-insertion test shows height n-1, demonstrating the degenerate worst case, with a one-line note on why balance (AVL/red-black) would fix it.
- Add delete(value) handling all three cases (leaf, one child, two children via in-order successor) and test that the BST invariant still holds afterwards via isValidBST.
- Implement iterative in-order traversal using an explicit stack (no recursion) and assert it produces the identical sequence to the recursive version.
- Add a self-balancing insert (AVL rotations or red-black) and re-run the sorted-insertion test to show height stays O(log n) where the plain BST was O(n).
- Add maxPathSum (tree DP allowing negative node values and any node-to-node path) and verify it against a tree with negative values where the optimal path skips a subtree.
This is the loop behind every tree problem you will meet again: a node is a value plus two subtrees, so insert, search, and the traversals are all recursion over that shape; correctness of the BST invariant needs an ancestor-propagated range, not a local glance; height, diameter, and balance are one-pass tree DP with a return value distinct from the answer; and the degenerate sorted-insertion case is the reminder that the invariant guarantees order, not balance. Building and testing it once makes the interview version and the production version muscle memory.