recursion

A tree question that's secretly a format-design question, which is why FDE loops love it. The preorder-with-null-markers trick is clean, but the delimiter and malformed-input follow-ups are where offers are decided.

The practical build that's secretly a graph problem: formulas are a dependency DAG, evaluation is DFS with memoization, and the three-color cycle trick decides whether A1=B1, B1=A1 crashes you or earns the offer.

Almost everyone writes the version that only compares each node to its immediate children, and almost every interviewer has a counterexample ready. The fix is to carry a valid (low, high) range down the recursion, or to check that an inorder traversal is strictly increasing.

The longest path between any two nodes need not pass through the root, which is what trips people up. The clean answer is one DFS that returns each node's height while updating a global best as it goes. First, nail down whether diameter counts edges or nodes.

A path can start and end anywhere and bends through at most one node, values can be negative, and you want the maximum sum. The move is a DFS that returns the best downward gain (clamped at zero) while a global max tracks the best path that bridges through each node.

The clean answer hinges on one insight: preorder names the root, inorder splits left from right. The trap is the O(n squared) version that slices arrays and scans for the root; the O(n) version uses a hashmap of inorder indices and passes bounds instead.

A two-part screen that looks like a warm-up and isn't. Part one is the classic stack validator with three bracket types; part two flips to generating every valid string of n pairs, and the Catalan count is the detail that catches people off guard.