Chapter 5 — Trees
Source:
src/main/kotlin/tree/(71 files — the biggest folder after arrays and graphs)Master idea: trees are recursive data structures — the root is a node whose children are trees. Almost every tree problem is “solve the left, solve the right, combine at the root” with a traversal order chosen deliberately.
Prerequisites: recursion, plus the two-pointer basics from Chapter 3 (for the iterative versions).
Problems at a glance (this chapter’s core set)
| # | Problem | Pattern | Complexity | Page |
|---|---|---|---|---|
| 5.1 | Maximum Depth Of Binary Tree | post-order recursion | $O(n)$ | → |
| 5.2 | Binary Tree Level Order Traversal | BFS with level fencing | $O(n)$ | → |
| 5.3 | Lowest Common Ancestor | post-order “found?” propagation | $O(n)$ | → |
| 5.4 | Binary Tree Maximum Path Sum | post-order with a global best | $O(n)$ | → |
| 5.5 | Serialize And Deserialize Binary Tree | pre-order + sentinels | $O(n)$ | → |
| 5.6 | Binary Tree Inorder Traversal (Iterative) | explicit stack | $O(n)$ | → |
| 5.7 | Construct Tree From Preorder And Inorder | index map + range recursion | $O(n)$ | → | | 5.8 | Binary Tree Right Side View | DFS first-per-level | $O(n)$ | → | | 5.9 | Path Sum III | prefix sums on a tree | $O(n)$ | → | | 5.10 | Diameter Of Binary Tree | post-order height + global best | $O(n)$ | → | | 5.11 | Recover Binary Search Tree | in-order swap detection | $O(n)$ | → | | 5.12 | All Nodes Distance K | parent map + 3-dir DFS | $O(n)$ | → | | 5.13 | Binary Tree ZigZag | level fence + addFirst | $O(n)$ | → | | 5.14 | Count Good Nodes | running-max DFS | $O(n)$ | → | | 5.15 | Populating Next Right Pointers | O(1)-space level threading | $O(n)$ | → | | 5.16 | Delete Node In A BST | successor splice | $O(h)$ | → | | 5.17 | Find Largest Value Per Row | BFS level max | $O(n)$ | → | | 5.18 | Sum Root To Leaf Numbers | carry-down DFS | $O(n)$ | → | | 5.19 | Recover A Tree From Preorder | depth-guided rebuild | $O(n)$ | → | | 5.20 | Range Sum Of BST | pruned traversal | $O(h+k)$ | → | | 5.21 | Longest Univalue Path | post-order chains | $O(n)$ | → | | 5.22 | Leaf-Similar Trees | leaf-sequence compare | $O(n)$ | → | | 5.24 | Inorder Successor In BST | successor-memory walk | $O(h)$ | → | | 5.25 | House Robber III | two-state tree DP | $O(n)$ | → | | 5.26 | Level Order Traversal II | BFS fence + reverse | $O(n)$ | → | | 5.27 | Unique Binary Search Trees | Catalan DP | $O(n^2)$ | → | | 5.28 | Unique Binary Search Trees II | Cartesian tree generation | $O(C_n)$ | → | | 5.29 | Lowest Common Ancestor III | parent-pointer climb | $O(d_p+d_q)$ | → | | 5.30 | Step-By-Step Directions | LCA + path strings | $O(n)$ | → | | 5.31 | Balanced Binary Tree | height check early exit | $O(n)$ | → | | 5.32 | Count Nodes Equal To Average | subtree pair | $O(n)$ | → | | 5.33 | Minimum Time To Collect All Apples | post-order cost DFS | $O(n)$ | → | | 5.34 | BST To Greater Sum Tree | reverse inorder | $O(n)$ | → | | 5.35 | Path Sum | target subtraction | $O(n)$ | → |
The rest of the tree/ directory
src/main/kotlin/tree/ is a forest: bst/ (Recover BST, BST Iterator, Inorder Successor, Delete Node, Unique BSTs, My Calendar…), bfs/ (Level Order II, Right Side View, Largest Value Per Row, Completeness, Averages…), segment/ (Segment Tree, Dynamic Segment Tree, Iterative Segment Tree…), fenwick/ (Fenwick Tree, Range Sum Query 2D Mutable…), mst/ (Prim’s & Kruskal’s on points), interval/, plus standalone classics (Diameter, Path Sum II/III, Zigzag, Vertical Order, Boundary, Symmetric, Construct from Pre+In / In+Post, Populate Next Right, All Nodes Distance K, Serialize N-ary, Maximum Product of Split, Count Good Nodes, etc.).
New pages are appended to the table above as they’re written.