Trees

Trees at Uber are the clean classics. The questions that come up have a tidy correct answer and a handful of edge cases. Those edges separate a working solution from one that crashes on a single node or miscounts a skewed chain. Three carry most of this slice: a Premium question of two nodes, a Premium question, and validating a binary search tree. All three are solved by walking the tree once with a recursion, and what changes between them is what each node hands back up and what extra fact it has to drag along.

The walk in every case is a depth-first search, meaning you go all the way down one branch before backing up to try the next, rather than sweeping the tree level by level. Two patterns cover the set. The first is a node that returns one value to its parent while the real answer accumulates in a variable off to the side, which is how diameter and a Premium question both work. The second is a node that carries a pair of bounds down into the recursion, a smallest and largest value it is allowed to be, which is how you validate a binary search tree. Name the shape before you type and each problem stops being about cleverness and becomes about getting the base case and the hand-off right.