Tree, BST, and trie · HTML
dfs(node) returns an identity for null, recursively obtains child summaries, computes upward_summary=combine(value,children), and may update global_answer using two or more child branches.
Recognition signals
- The input is a rooted tree or can be given parent-child structure.
- A node answer depends on completed subtree information.
- The parent needs a compact height, sum, boundary, or single extendable path.
- A global structure may connect multiple child subtrees at one node.
- Postorder naturally provides children before parent.
False friends
| Signal | Why it is different |
|---|
| Layer-based or nearest-depth output | Level-order BFS directly exposes complete depth boundaries. |
| Several mutually exclusive modes per node | When one summary is insufficient, use a vector of tree-DP states. |
| Aggregation paths in a general graph | Cycles and shared subgraphs break independent subtrees; use graph or DAG machinery. |
Core invariant
dfs(u) returns a summary concerning only u's subtree and satisfying its parent contract; before return, every global candidate fully contained in that subtree has been considered.
State, transition, and processing order
| Item | Definition |
|---|
| State | The current node, child summaries, and either a separate global accumulator or a structured return value. |
| Transition | Recurse into children, compute node-local complete candidates, update the global answer, and build one upward summary. |
| Frontier / order | Postorder on the recursion stack; a null identity unifies leaf transitions. |
Python skeleton
def tree_diameter(root):
best = 0
def height(node):
nonlocal best
if node is None:
return 0
left = height(node.left)
right = height(node.right)
best = max(best, left + right)
return 1 + max(left, right)
height(root)
return best
Correctness sketch
- A null subtree has height zero, satisfying the return contract.
- Assuming child heights are correct, an upward path through this node can choose only the taller child, so its height is 1+max.
- A path whose highest connector is this node uses left+right; every cross-subtree path has one such connector, making the global maximum complete.
Complexity
| Time | Space | Parameters |
|---|
| O(n) when combine costs O(node degree) | O(h) recursion stack, worst-case O(n) | n is node count and h tree height. |
Edge cases
- empty tree
- diameter measured in edges versus nodes
- a deeply skewed tree
- identity with negative weights
- top two children in an n-ary tree
- global accumulator reused across calls
Error patterns
| Pattern | Why it fails / fix |
|---|
| Returning the complete global optimum upward | A path joining two children cannot also extend through the parent; separate complete and extendable values. |
| Aggregating in preorder | Child summaries are unavailable, so the node result is incomplete. |
| Using the wrong null identity | Height, sum, extrema, and negative path objectives need different neutral values or sentinels. |
| Rescanning a subtree at every node | That turns O(n) into O(n²); return each reusable summary once. |
Selection and exclusion rules
- Define exactly what the parent needs returned.
- Separate upward-extendable summaries from complete global candidates.
- Choose a null identity matching the combine operation.
- Use iterative postorder for trees beyond safe recursion depth.
Original micro-example
| Part | Detail |
|---|
| Result | The complete candidate joins both sides, while the upward summary retains one, so their meanings differ. |
| Setup | A root has a left chain of height 2 and a right chain of height 1. |
| Trace | The complete path through the root has 2+1=3 edges; the upward summary keeps only one side as height 1+max(2,1)=3. |
Recall prompts
My notes