Trees, Linked Lists, And Pointer Algorithms

What's being tested

These problems test pointer-based traversal, in-place state updates, and edge-case-safe algorithm implementation across trees, linked lists, and numeric routines. For an MLE, the signal is whether you can write production-quality code for core data structures without relying on library shortcuts.

Patterns & templates

• Fast exponentiation — implement `pow`(x, n) with exponent halving in O(log n) time; handle n < 0, INT_MIN, x == 0.

• Floyd cycle detection — use slow and fast pointers; after collision, reset one pointer to head to find cycle entry in O(n).

• Tree level traversal — use queue BFS for left-side view; first node per level is answer, O(n) time and O(width) space.

• DFS with depth tracking — pre-order left-first recursion records first value at each depth; simpler code, but stack can hit O(height).

• In-order successor with parent pointers — if right child exists, return leftmost right subtree; otherwise climb until leaving a left edge.

• Perfect binary tree neighbor linking — use already-established next pointers level by level; achieve O(n) time and O(1) extra space.

• Constant-time board state tracking — maintain row, column, diagonal counters; update each move in O(1) instead of rescanning n×n.

Common pitfalls

Pitfall: Treating negative exponents as 1 / pow(x, -n) can overflow for INT_MIN; cast to long before negation.

Pitfall: For tree views, confusing “leftmost node per level” with “always follow left children” fails on missing-child and skewed cases.

Pitfall: In linked-list cycle detection, stopping at the meeting point gives only cycle existence, not the cycle entry.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.