Recap: Tree Patterns

Pass down what the path knows, return up what the subtree holds, record what bends through a node, and use a queue when the levels are the answer.

A tree pattern decides three things for one recursive visit: what each call is handed by its parent, what it hands back, and what it records on the way. A question about the path to a node passes values down, a question about what lies below returns them up, and a question about the levels themselves uses a queue. Heights and depths count edges throughout:

Tree questions and what each call passes, returns and records
Question	Passed down	Returned up	Recorded	Traversal	Cost
Depth of every node	Depth	Nothing	Each depth	Recursion, node first	O(n)
Height of the tree	Nothing	Height, −1 when empty	Nothing	Recursion, children first	O(n)
Longest path	Nothing	Height	Left + right + 2	Recursion, children first	O(n) time, O(h) stack
Lowest common ancestor	The two nodes	Found node or nothing	Nothing	Recursion, stops at a target	O(n)
Each level as a group	Nothing	Nothing	Queue size per level	Queue, level by level	O(n) time, O(w) space
Save and rebuild	Nothing	The subtree built	The line, # for empty	Preorder with markers	O(n)

Measuring a height at every node instead of returning it costs O(n²) on a chain, and returning the bent path instead of the height reports a path that cannot exist. Recursion on a chain-shaped tree is as deep as the tree, so a very deep tree in Python needs a stack of its own or a queue.

← → move through sections and cards