Recursion and Trees
Retrieval: which traversal, which direction?
Two problems rebuilt cold, plus the three questions that decide the shape of any tree solution.
Key idea
Ask these before writing anything
Does the question care about levels? If yes, use a queue and snapshot its length. If no, recursion is almost always shorter.
Does a node need something from above, something from below, or both? From above is a parameter, from below is a return value, and both is both. Naming them turns the function signature into a decision rather than a guess.
Is the answer necessarily rooted at the node it passes through? If not, you need the two-quantity split: return one thing, update another.
Tip
And one more for search trees
If the tree is a search tree and your solution visits every node, look again. The ordering usually lets you descend one path instead, and in-order traversal usually turns the question into one about a sorted sequence.
What shape does this need?
Find the largest sum of any root-to-leaf path in a binary tree whose values may be negative. What shape does the solution take?
Diameter of Binary Tree, from scratch
You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.
LRU Cache, from scratch
You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.