DEV Community: codeintuition

Tree Traversal: Why the Order You Pick Is a Data Flow Decision

Prakhar Srivastava — Thu, 28 May 2026 11:13:38 +0000

Tree traversal usually gets taught as three separate algorithms to memorize: preorder, inorder, postorder. They are not three algorithms. They are one recursive function with a single line moved to a different spot, and that one line decides which problems you can solve.

I watched this trip up people prepping for months. They had all four traces memorized and still froze when a new problem asked them to pick an order. The trace is the easy part. Knowing which order hands you the information you need is the part that actually matters in an interview.

TL;DR: Traversal visits every node once. The four standard orders differ only in when the current node gets processed relative to its children. Preorder processes the node before its children, postorder after, inorder between, and level order goes breadth first with a queue. Pick the order by asking which direction data has to move between a parent and its children.

The four orders on one tree

Run all four on the same tree and the difference stops being abstract.

Preorder (node, left, right): 1, 2, 4, 7, 5, 3, 6
Inorder (left, node, right): 7, 4, 2, 5, 1, 3, 6
Postorder (left, right, node): 7, 4, 5, 2, 6, 3, 1
Level order (breadth first): 1, 2, 3, 4, 5, 6, 7

Inorder looks unsorted here because this is not a binary search tree. The sorted property only shows up when the values obey the BST invariant of left less than node less than right. On a plain binary tree, inorder still walks left, node, right, but the numbers come out in whatever order the structure gives you.

The only thing that changes is one line

The three depth first orders are the same code. The recursive call structure is identical. The only difference is where the line that processes the node sits relative to the two recursive calls.

def preorder(node):
    if not node:
        return
    process(node)        # before the children
    preorder(node.left)
    preorder(node.right)

def inorder(node):
    if not node:
        return
    inorder(node.left)
    process(node)        # between the children
    inorder(node.right)

def postorder(node):
    if not node:
        return
    postorder(node.left)
    postorder(node.right)
    process(node)        # after the children

Move one line, change the order. That is the whole trick for the depth first family.

Why postorder is the one that computes heights

This is where order stops being trivia. Take the height of a binary tree. To know a node's height, you need the heights of both children first. You take the larger child height and add one. That dependency, children before parent, is exactly what postorder gives you.

def height(node):
    if not node:
        return -1            # an empty subtree has height -1
    left = height(node.left)
    right = height(node.right)
    return max(left, right) + 1

Trace it on the tree above and watch every node wait for its children before it can answer.

Node 7: leaf                      -> 0
Node 4: left(7)=0, no right       -> max(0, -1) + 1 = 1
Node 5: leaf                      -> 0
Node 2: left(4)=1, right(5)=0     -> max(1, 0) + 1 = 2
Node 6: leaf                      -> 0
Node 3: no left, right(6)=0       -> max(-1, 0) + 1 = 1
Node 1: left(2)=2, right(3)=1     -> max(2, 1) + 1 = 3

Try the same thing with preorder and you hit the parent first, with no information about the subtree below it. You can still make it work by passing depth down as a parameter and tracking a maximum in an outer variable, but it is fifteen awkward lines where postorder is five. Diameter, subtree sums, balanced checks, distributing coins: same shape every time. The parent cannot answer until both children have reported back, so you process the children first.

The first time I had to write any of these iteratively under a timer, I realized I had memorized the recursion and never the stack sitting under it. That gap is part of why I built Codeintuition, and the binary tree course traces the stack state for the iterative versions one frame at a time.

Level order is the odd one out

Level order is the only one that is not depth first. It uses a queue, not the call stack. Enqueue the root, then repeatedly dequeue a node and enqueue its children. Nodes come out one full level at a time.

from collections import deque

def level_order(root):
    if not root:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        process(node)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

Anything that works on nodes at the same depth (level sums, zigzag traversal, connecting nodes across a level) needs this breadth first access. Forcing depth first to do the same job means tracking depth by hand, which is more bookkeeping than the problem deserves.

Picking the order: which way does the data flow?

Almost every tree problem opens with the same hidden question. Does the parent need answers from its children, or do the children need data handed down from the parent? Answer that and the order falls out.

Postorder: the parent needs results from both children (height, diameter, subtree sums, balanced checks)
Preorder: the children need data passed down from the parent (root to leaf path sums, serialization)
Inorder: you want values in sorted order out of a BST
Level order: the work happens per level (level sums, zigzag, connecting same depth nodes)

A quick aside worth its own paragraph: there is a real argument that some problems read fine in more than one order, and reconstructing a tree from traversals is its own rabbit hole (preorder alone is not enough, you need inorder too, or null markers). That is a separate post. For the day to day of picking an order on sight, the data direction question settles it.

Listing the four orders is the easy part of this topic. Looking at an unfamiliar tree problem and knowing which order hands you the right information before you write a line is the skill that actually transfers to an interview, and it comes from understanding why each order exists, not from re-reading the traces.

I wrote a longer version on my own blog that walks through the iterative conversions for all three depth first orders.

Which traversal order was the one that finally made sense to you only after you got burned picking the wrong one on a real problem?

Binary Tree Recursion in Interviews: The Call Stack Diagnostic

Prakhar Srivastava — Tue, 26 May 2026 16:07:59 +0000

I've watched plenty of engineers explain binary tree traversals on a whiteboard and then freeze five minutes into an unfamiliar tree problem. The gap isn't conceptual. They know what preorder, inorder, and postorder mean. They can sketch a BST. What they can't do is predict, in their head, how the call stack will branch when a recursive function meets a tree's shape.

That's the real skill tree interview problems test. And once you can do it, the patterns stop feeling like 14 separate things to memorise.

TL;DR

Tree problems test whether you can mentally simulate the call stack's shape before writing code.

The six traversal patterns split along one axis: which direction does information flow?

Down through parameters, up through return values, or sideways across siblings.

Get the direction right and the solution writes itself.

Get it wrong and you spend the interview debugging recursion that looks correct at every node.

Why arrays don't prepare you for trees

When you scan an array, you hold the whole traversal in your head as a walk from left to right. One element at a time. Your mental model is a line.

Trees break that completely. At every node, execution splits into two branches, and each of those branches splits again. The call stack grows in a shape you can't flatten. To predict what your code does, you have to think in the shape of the tree itself.

This is why someone can solve medium array problems comfortably and still stumble on easy tree problems. The mental simulation load is qualitatively different. You're tracking which branch you're in, what state you carried down, and what values are coming back up.

The call stack is a concrete thing, not a metaphor

Before you can simulate tree recursion, you have to know what's physically happening in memory when a recursive function runs. The call stack is a real structure in your program's memory, not a teaching analogy.

Every function call pushes a stack frame. The frame holds the function's local variables, parameters, and the return address. When the function returns, the frame pops and the frame below resumes exactly where it left off.

Walk through factorial(4) and the stack looks like this at maximum depth:

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

| factorial(1) |  <- top, currently executing
| factorial(2) |  <- waiting on factorial(1)
| factorial(3) |  <- waiting on factorial(2)
| factorial(4) |  <- original call, waiting on result

Each frame keeps its own n. Nothing shared. When factorial(1) returns 1, that frame pops. factorial(2) resumes, computes 2 * 1, returns 2. The chain unwinds until factorial(4) returns 24.

I'd recommend stepping through this in a debugger once. Watching frames push and pop in real time teaches more about recursion in ten minutes than an hour of reading explanations. Most engineers I see prep have never done this, and it changes how you predict what recursive code will do.

Now extend the same idea to a binary tree. Each node makes two recursive calls instead of one. The stack still pushes and pops frame by frame, but the shape it traces is no longer a straight line down and back up. It's the branching shape of the tree itself. Predict that shape correctly and the solution becomes mechanical.

The information flow diagnostic

Every tree problem maps to one of six traversal patterns. The patterns split cleanly when you ask a single question:

Which direction does information have to flow to solve this problem?

Down (preorder). State is carried from parent to children through function parameters. The node is processed before its children. Useful when each node's computation depends on what came before it on the path from the root.
Up (postorder). Children are processed first, and their results bubble up through return values. The node is processed after its children. Useful when the answer at each node depends on its subtrees.
Sideways (level order). Nodes at the same depth are processed together before moving to the next level. The call stack doesn't help here. You want a queue.

That diagnostic alone resolves most pattern-selection questions in under 30 seconds.

The six patterns are refinements of the three directions:

Stateless preorder: pure top-down. No accumulator. No return value carrying anything.
Stateful preorder: top-down with a shared accumulator that mutates on descent.
Stateless postorder: pure bottom-up. Each subtree's result is a function of its children's results.
Stateful postorder: bottom-up with a global side effect updated from subtree results.
Root to leaf path: top-down accumulation, evaluation only at leaves.
Level order: queue-based BFS, not recursion at all.

Stateful postorder is the hardest of the six. The return value at each node is what the parent needs, but the answer to the problem lives in a global variable updated as a side effect. Tree diameter is the textbook example. Each call returns subtree height, but the diameter (the actual answer) accumulates separately as the maximum of left_height + right_height seen at any node.

BST validation, the recursion that looks correct but isn't

A binary search tree adds one invariant to the binary tree: every value in the left subtree is smaller than the node, every value in the right subtree is larger. That single rule lets you do things on a BST that aren't possible on a general binary tree.

The most natural use of the invariant is inorder traversal, which visits BST nodes in sorted order. Left subtree, then node, then right subtree. The traversal physically walks the sorted sequence.

BST validation is where most people write the wrong recursion. The instinctive version checks each node against its direct children.

# Wrong: checks only direct parent-child constraints
def is_valid_bst(root):
    if not root:
        return True
    if root.left and root.left.val >= root.val:
        return False
    if root.right and root.right.val <= root.val:
        return False
    return is_valid_bst(root.left) and is_valid_bst(root.right)

Consider the tree [10, 5, 15, null, null, 6, 20]. Every direct parent-child pair is locally fine. 5 < 10. 15 > 10. 6 < 15. 20 > 15. The naive recursion returns True. But the tree is invalid, because 6 sits in the right subtree of 10 and 6 < 10 violates the BST invariant against its ancestor.

The correct recursion uses inorder traversal and tracks the previously visited value. If the inorder sequence is strictly increasing, the tree is a valid BST.

def is_valid_bst(root):
    prev = float('-inf')

    def inorder(node):
        nonlocal prev
        if not node:
            return True
        if not inorder(node.left):
            return False
        if node.val <= prev:
            return False
        prev = node.val
        return inorder(node.right)

    return inorder(root)

On the same tree, inorder visits 5, 10, 6, 15, 20. When it reaches 6 with prev = 10, the check 6 <= 10 fires and returns False. The mechanism that makes this work is that inorder converts the ordering invariant into a single forward-walking check across the entire tree. The naive version only checks two-node relationships and misses every ancestor violation.

The four BST-only patterns

The ordering invariant opens four traversal strategies that don't exist on general binary trees:

Sorted traversal: use inorder for problems where the BST's ascending order is the answer. Validation, conversion to a sorted array, conversion to a doubly linked list.
Reverse sorted traversal: visit right, then node, then left, for descending order. Kth largest, ranking, enriched sum trees.
Range postorder: prune entire subtrees by comparing the node's value against a range. If the node sits below the range, skip its left subtree entirely. This is where BSTs get their logarithmic performance on range queries.
Two pointer on BST: run a forward iterator (inorder) and a reverse iterator (reverse inorder) simultaneously. Two sum on a BST, finding the median, pair sum problems.

For heaps, two patterns cover most of what interviews ask. Top K elements maintains a heap of size K (a min heap to track the K largest, counterintuitively). The comparator pattern uses custom ordering when "priority" isn't the raw value, which covers K most frequent, K smallest pairs, K closest points, and K way merge.

The mistakes I see most often

Across the engineers I help prep, the same handful of mistakes show up:

Confusing preorder and postorder state. You try to compute tree height by passing depth down through parameters, when height has to aggregate up from children through return values.
Forgetting to capture the return value. Writing postorder(node.left) without assigning the result. The recursive call executes, but the computed information evaporates.
Mixing global and local. The function returns a local value (the subtree's result for the parent) while a global accumulator holds the actual answer. Diameter is the classic case. Confuse the two and the recursion looks right at every node but the answer comes out wrong.
Using recursion for level order. Level order is breadth first by nature, and recursion is depth first. You can simulate level order with recursion plus a depth parameter, but a queue-based BFS is cleaner and what interviewers expect.
Skipping the subproblem definition. Before writing any recursive function, answer in one sentence what f(node) returns. If you can't, the recursion will fail.
Forgetting the null base case. Null children show up everywhere in binary trees. A leaf has two null children. Forgetting to handle them is the most common runtime error in tree solutions.
State not undone on backtrack. In root to leaf path problems, you append to a path list on descent. If you don't pop on return, the path accumulates stale entries from sibling branches.

How to practice the simulation skill

Mental simulation isn't built by solving more problems. It's built by predicting the call stack's shape before running the code, and then verifying the prediction.

Take a problem you've solved before. Cover the solution. Sketch the tree. Predict the call sequence on paper. Now run the solution in a debugger and step through frame by frame. Note where your prediction diverged from what actually happened.

That divergence is the gap interviews test under pressure. Every problem you do this on builds the simulation skill directly. After about ten rounds, the prediction step stops being a separate exercise and starts running automatically as you read the problem statement.

That's the gap I built Codeintuition to close. The binary tree course walks through the call stack frame by frame on every pattern, so the simulation becomes something you've already done dozens of times rather than something you're constructing from scratch under interview pressure.

I wrote a longer version on my own blog that covers the BST sorted traversal family and the heap patterns I skipped here.

Which pattern was the one that finally made the call stack visible in your head? Mine was stateful postorder, the first time I traced diameter by hand.

Binary Tree Interview Problems: 6 Traversal Patterns, 15 Problems

Prakhar Srivastava — Mon, 25 May 2026 12:01:59 +0000

The default tree prep is sorting LeetCode's tree tag by acceptance rate, doing the top 40, and hoping the patterns transfer. They mostly don't. Tree problems feel unpredictable because the practice was organised by popularity, not by mechanism. Every binary tree interview problem is moving information through the tree in one of six ways, and once the six are visible, fifteen problems give more coverage than forty random ones.

TL;DR: Binary tree interview problems cluster around six traversal patterns: preorder, postorder, root to leaf, level order, lowest common ancestor, and simultaneous traversal. Two problems per pattern is enough for interview-grade coverage. The trick is to practice in pattern order, not difficulty order.

The six patterns that cover the binary tree interview space

Every tree problem is a question about how information has to move. Preorder pushes information down from parent to child. Postorder pushes it up from child to parent. Root to leaf accumulates state along a single path. Level order processes nodes layer by layer with a queue. Lowest common ancestor is about which subtrees contain which targets. Simultaneous traversal walks two trees in parallel to compare or merge structure.

Preorder. Information flows down. Pass current state into the recursive call.
Postorder. Information flows up. Compute the answer from what the children return.
Root to leaf. State accumulates along a path. Backtrack after each child.
Level order. Use a queue. Process all nodes at depth d before any at depth d+1.
Lowest common ancestor. Recursive search. Return a target on the way back up.
Simultaneous traversal. Two trees, one walk. Compare or merge at every step.

Two problems per pattern is the right calibration. The first problem teaches the mechanism. The second forces a variation that reveals whether the mechanism transferred or got memorised. Past two, the marginal practice value drops fast, because the third problem in a pattern usually just rehearses what the second one already established.

Stateful postorder, where the medium and hard problems live

Most of the medium and hard binary tree problems are stateful postorder. The recursion returns something the parent needs (usually height), but the answer lives in a variable updated at each node. That split between "what the function returns" and "what you care about" is what makes the pattern hard to grasp from one problem alone.

Diameter is the cleanest place to see it. The diameter of a binary tree is the longest path between any two nodes, measured in edges. The path can pass through the root or be entirely inside a subtree. The recursion has to return the height of each subtree (so the parent can compute its own height), but the answer (longest path) is computed at each node as left_height + right_height and tracked separately.

def diameter(root):
    longest = 0

    def height(node):
        nonlocal longest
        if node is None:
            return 0
        left_h = height(node.left)
        right_h = height(node.right)
        longest = max(longest, left_h + right_h)
        return 1 + max(left_h, right_h)

    height(root)
    return longest

Two things to notice. First, the function is named height, not diameter. That naming is deliberate. The recursion is computing height, and diameter falls out as a side effect at each node. Second, longest is a nonlocal variable, which is the Python way to track an answer outside the recursive frame. In other languages you'd use an instance variable or a single-element list. The mechanism is the same.

Once the diameter mechanism clicks, half a dozen other problems unlock with no extra learning. Distribute coins tracks surplus or deficit at each subtree while a global counter tracks total moves. Longest monotonic path tracks the longest increasing and decreasing chain at each node while a global tracks the overall longest. Maximum path sum tracks the best downward path from each node while a global tracks the best path that bends through any node. Same skeleton, different state.

The diameter lesson walks the recursion variable by variable, which is the depth that makes the "function returns one thing, answer lives elsewhere" framing stick. The framing is what transfers, not the specific problem.

The 15 problems, grouped by pattern

The list below is what comes out when you group binary tree interview problems by mechanism instead of by popularity or difficulty. Two problems per pattern. The first is the direct application, the second is the variant that proves the mechanism transferred.

Preorder (information flows down):

Sum of path. Stateless preorder. Pass the remaining target sum down, check for zero at a leaf.
Right view. Stateful preorder. Pass depth down, track the deepest depth seen so far globally.

Postorder (information flows up):

Height of binary tree. Stateless postorder. Return 1 + max(left, right).
Diameter of tree. Stateful postorder. Return height, track longest path globally.

Root to leaf (state accumulates along a path):

Root to leaf paths. Enumerate every path. Backtrack after each recursive call.
Equal paths. Check whether any path sums to a target. Validate only at leaves.

Level order (queue, layer by layer):

Level sum. Sum the values at each depth.
Zigzag traversal. Alternate left-to-right and right-to-left per level.
Vertical traversal. Group nodes by (column, row) coordinates.

Lowest common ancestor (multi node reasoning):

LCA. Find the deepest shared ancestor of two target nodes.
Distance between nodes. Compose LCA with depth-from-LCA.

Simultaneous traversal (two trees, one walk):

Identical trees. Compare both trees node by node in lockstep.
Subtree detection. Run identical-trees from every node of the larger tree.

Three additional postorder problems (distribute coins, longest monotonic path, maximum path sum) sit alongside diameter as variants of the same stateful skeleton. Adding any of them to your list gives diminishing returns once diameter is solid, which is why the 15-problem cut works.

Why pattern order beats difficulty order

The conventional advice is to do easy problems first, then mediums, then hards. For binary tree interview problems specifically, that ordering is wrong. A medium postorder problem can be easier than a hard preorder problem if you already understand preorder and haven't met postorder yet. The skill that transfers is the pattern mechanism, not the difficulty class.

Pattern order looks like this:

Preorder before postorder, because preorder is what most people already do intuitively when they imagine walking a tree.
Postorder before root to leaf, because root to leaf borrows the return mechanism from postorder.
Root to leaf before level order, because level order is a different paradigm (queue based) and benefits from the recursive patterns being solid first.
Level order before LCA, because LCA is multi node reasoning and the single-walk patterns have to feel automatic first.
LCA before simultaneous traversal, because simultaneous traversal scales LCA-style reasoning to two trees instead of two nodes.

Within each pattern, do the direct application first and the variant second. Height before diameter. LCA before distance between nodes. Identical trees before subtree detection. If you can't trace the solution to the direct application on paper without running the code, the variant won't transfer either.

Three recursion mistakes that derail tree rounds

These come up across most tree rounds I see, in roughly this order under interview pressure.

Returning the answer when the parent needs supporting information. The "what does the recursion return?" question is the one most candidates get wrong on stateful problems. In longest monotonic path, the function needs to return the longest increasing and decreasing chains so the parent can extend them. The actual answer (longest path overall) gets updated at each node by combining left and right chains. If you try to return the answer directly, the parent can't use it to extend its own chain.
Missing the backtrack in path enumeration. Root to leaf paths shares a path list across recursive calls. If you don't remove the last element after each child returns, earlier paths bleed into later ones. The output looks almost right, which is what makes the bug expensive to diagnose mid-interview.
Wrong base case for the problem. if not node: return 0 is correct for height because the height of a null subtree is zero. It is wrong for equal paths, where you need to distinguish between "node is null" and "node is a leaf." Returning at null makes you incorrectly treat the null children of single-child nodes as valid leaves. The fix is to add an explicit leaf check before the null check, or to handle the null case as "no path here, ignore" rather than "valid empty path."

The pattern in all three is the same. The mechanism is right, but the boundary handling is wrong, and the failure mode is "passes most test cases, breaks on the edge case the interviewer planted on purpose."

The 6-pattern framing is the thing I keep coming back to in how I think about tree prep on Codeintuition, because grouping by mechanism is what turns 15 problems into 15 instances of recognisable techniques instead of 15 stand-alone puzzles. Most tree practice I see does the opposite: 40 problems, none of them grouped, and the candidate ends up freezing on the next unfamiliar one anyway.

I wrote a longer version on my own blog that walks each pattern through its two problems and includes the recursion-bug catalogue with worked examples.

Which tree pattern did the most for you, where one or two problems unlocked a dozen variations you didn't have to memorise?

Binary Search Tree Explained: All Operations From One Rule

Prakhar Srivastava — Mon, 25 May 2026 09:08:49 +0000

Most BST tutorials teach search, insert, and delete as three procedures. You memorise one, then the next, then the three deletion cases. Then deletion shows up in an interview and the whole stack collapses, because what got memorised was the sequence of steps and not the rule the steps were trying to preserve.

TL;DR: A binary search tree is defined by a single ordering invariant: every node's left subtree contains smaller values and every right subtree contains larger ones. Search, insert, and delete are all derivable from that rule. Treat the invariant as primary and the procedures stop being three things to memorise.

The one rule the whole data structure hangs on

A BST is a binary tree where every node's left subtree contains only smaller values and every right subtree contains only larger values. That is the entire data structure. One ordering invariant, nothing else.

The invariant gives the tree something arrays and linked lists can't give: a way to eliminate half the remaining work at every step. When you're looking for a value, you compare it to the current node and pick a direction. You never look at the other side. The same halving idea that makes binary search fast on sorted arrays, except the tree structure also makes insertion and deletion cheap because nothing has to shift.

A useful framing: every BST operation is the same recursive walk. The walk asks one question at each node (target vs current), takes one of two branches, and stops at some terminal condition. What changes between operations is the terminal condition and what happens when you reach it.

Search and insert: one walk, two endings

Start with a BST holding [8, 3, 10, 1, 6, 14] and search for 6. From the root, 6 < 8, go left to 3. Then 6 > 3, go right and land on 6. Three comparisons, three levels. The right subtree of 8 was never touched.

Now insert 7 into the same tree. From the root, 7 < 8, go left. Then 7 > 3, go right to 6. Then 7 > 6, go right again and land on a null pointer. Create node 7 there. Same walk, different ending. Search stops when the target matches or the pointer is null. Insert stops when the pointer is null and writes a new leaf.

def search(node, target):
    if node is None or node.value == target:
        return node
    if target < node.value:
        return search(node.left, target)
    return search(node.right, target)

def insert(node, value):
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)
    return node

Read the two functions side by side. The structure is identical. The terminal action differs by a single line. That is the derivation.

Insert always creates a leaf. It never restructures the existing tree, which is what makes it cheap. It is also what eventually makes the tree fragile, since nothing pushes back when an input order produces an unbalanced shape.

Deletion: three cases collapsed to one question

Deletion is where most candidates lose the thread, because removing a node can violate the invariant. The standard explanation gives you three cases and tells you which procedure to run for each. The better framing is one question with three answers.

The question is: how do I fill the gap left by the removed node without breaking left < node < right?

If the node is a leaf, the answer is nothing. Drop the pointer to it. Done.
If the node has one child, the answer is to promote that child. The child's subtree already satisfies the invariant relative to the deleted node's parent, so promotion preserves the rule.
If the node has two children, the answer is to find a replacement that is structurally allowed to sit in that slot. That replacement is the inorder successor (the smallest value in the right subtree), or symmetrically the inorder predecessor.

The two child case is the one that trips people up. You can't promote one child arbitrarily, because the other child's subtree would end up misplaced. The successor works because it is the smallest value larger than the node being deleted, which is what the position requires after the node is gone. Copy its value into the deleted node's slot, then delete the original successor from its own location. The successor has at most one child (it is the leftmost node in a subtree, so its left pointer is null by construction), and removing it falls into case 1 or case 2.

Trace deleting node 3 from [8, 3, 10, 1, 6, 14, 4]:

Step 1: Find node 3. It has two children (1 and 6). Two child case.
Step 2: Find inorder successor of 3.
        Go right to 6, then left to 4.
        Node 4 is the smallest value in 3's right subtree.
Step 3: Copy 4's value into node 3's slot.
Step 4: Delete the original node 4 from its previous position.
        Node 4 was a leaf. Drop the pointer.

Result:
        8
       / \
      4   10
     / \    \
    1   6   14

Verify the invariant holds: 1 < 4 < 6 in the left subtree, 4 < 8 < 10 across the root, 10 < 14 on the right. The deletion preserved the rule.

def delete(node, value):
    if node is None:
        return None
    if value < node.value:
        node.left = delete(node.left, value)
    elif value > node.value:
        node.right = delete(node.right, value)
    else:
        if node.left is None:
            return node.right
        if node.right is None:
            return node.left
        successor = node.right
        while successor.left is not None:
            successor = successor.left
        node.value = successor.value
        node.right = delete(node.right, successor.value)
    return node

The recursive call inside the two child branch is the only piece of the procedure that isn't immediately obvious. It is the same delete walking into the right subtree to remove the successor, which is guaranteed to be a leaf or a single child node and so resolves into one of the first two branches.

Why deletion is where interviews break

Search and insert can be passed by sketching the walk on paper and following the comparisons. Deletion can't, because the two child case requires you to articulate why the inorder successor specifically is the right replacement. That articulation reveals whether you understand the invariant or just memorised three procedures.

I keep seeing the same failure mode. The candidate handles the leaf case and the single child case, then stalls on the two child case. They reach for an arbitrary replacement, realise something is off, and try to patch the resulting violation downstream. The patch usually breaks a different invariant somewhere else, the trace gets longer, and the clock runs out.

The fix isn't to memorise the inorder successor trick harder. The fix is to be able to answer "why this specific replacement?" If you can say "the inorder successor is the smallest value larger than the deleted node, which is what the slot requires after deletion," you'll derive the procedure from the rule in real time. If you can't, you'll keep losing the thread the moment the interviewer adds a constraint.

When the invariant holds but the speed doesn't

Every BST operation runs in O(h) time where h is the tree's height. The marketing claim is O(log n), but that only holds when the tree stays balanced. A plain BST has no mechanism to enforce that.

Insert [1, 2, 3, 4, 5] into an empty BST in that order and you get this:

The invariant is technically satisfied. Every left subtree is empty, every right subtree contains larger values. But the tree is structurally a linked list. Search degrades to O(n). The performance promise comes from balance, and balance comes from input order. Sorted input is the worst possible input for a plain BST.

The fix is a self balancing variant such as AVL or Red-Black trees, which add rotation logic that restructures the tree after each insertion to guarantee O(log n) height regardless of input order. In an interview, if you state "BST operations are O(log n)" without qualifying balance, you'll lose points. The honest answer is "O(log n) on a balanced tree, O(n) worst case, and balance is not automatic on a plain BST."

Where candidates trip up under pressure

These are the patterns I see derail BST questions in interviews, roughly in the order they show up.

Checking only immediate children for the invariant. The rule is not left child < node < right child. It is every node in the left subtree is smaller. A value can pass the immediate-children check and still violate the constraint against a grandparent. The BST validator lesson covers why you have to pass upper and lower bounds down through the recursion to catch this.
Confusing BST ordering with heap ordering. A BST orders left-to-right (left < node < right). A heap orders parent-to-child (parent > children in a max heap). Mixing them up sends you walking the wrong direction during search.
Stalling on two child deletion. Two child deletion is the case interviewers probe deliberately. If you've practiced naming the inorder successor and stating why it works, you've already reduced the case to a previously solved one.
Asserting O(log n) without qualifying balance. The interviewer doesn't want to hear "BST operations are logarithmic." They want to hear "logarithmic when balanced, linear in the degenerate case, and here's what causes the degenerate case." That sentence reveals whether you've thought about the invariant or just memorised the headline.

The BST work was where the "derive from the invariant, don't memorise the procedure" framing first clicked for me when I was building Codeintuition's learning path. Most candidates I see practice the procedures three times and the invariant zero. Flipping that ratio is the part that compounds, because once the invariant is the unit of memory, every operation that respects the invariant becomes derivable on the spot.

I wrote a longer version on my own blog that walks the inorder traversal proof and the recursive construction of a balanced BST from a sorted array.

Which BST operation finally clicked for you only after sketching the tree on paper instead of reading another explanation?

Big O Notation Explained: Derive It, Don't Memorize It

Prakhar Srivastava — Sat, 23 May 2026 11:26:16 +0000

You can recite that binary search is O(log n) and nested loops are O(n²). That recitation stops helping the moment an interviewer writes an unfamiliar function on the whiteboard and asks you to analyse it. The useful version of Big O is the one you can derive, not the one you can look up.

TL;DR: Big O describes how an algorithm's work grows as input size grows. The interview skill isn't naming complexities from memory. It's counting how many times the dominant operation runs as a function of input size and watching what dominates as the input gets large.

What Big O actually measures

Big O describes the upper bound on how an algorithm's running time or space usage grows as its input grows. That word, grows, is the one that matters. It doesn't tell you that binary search takes exactly 20 comparisons on an array of a million elements. It tells you that doubling the array adds roughly one more comparison. The relationship between input and work is the thing being measured.

There are two simplifications Big O does on purpose. It drops constants, so O(3n) becomes O(n). And it drops lower-order terms, so O(n² + n) becomes O(n²). Both simplifications stop mattering at scale, which is the only scale the notation is built for. If n is 10, the constants matter. If n is 10 million, the highest-order term swallows everything else.

The "upper bound" piece is the worst case. An algorithm marked O(n²) might finish faster on certain inputs. It just won't do worse than quadratic. Worst-case behaviour is what interviewers care about because best-case behaviour doesn't protect you from the input that breaks the solution.

The five growth classes you'll actually see

Every algorithm you'll meet in an interview lives in one of these.

Complexity	Name	n=10	n=1,000	n=1,000,000
`O(1)`	Constant	1	1	1
`O(log n)`	Logarithmic	3	10	20
`O(n)`	Linear	10	1,000	1,000,000
`O(n log n)`	Linearithmic	33	10,000	20,000,000
`O(n²)`	Quadratic	100	1,000,000	1,000,000,000,000

The jump from O(n) to O(n²) is where most interview problems live. A brute-force solution that checks every pair in an array is quadratic. The optimised version using a hash map or two pointers drops it to linear. At a million elements, that's the difference between a million operations and a trillion.

O(n log n) is worth a side note. It's the theoretical floor for comparison-based sorting. Merge sort, heapsort, well-implemented quicksort all sit there. The number isn't arbitrary. It falls out of information theory.

Where the derivation skill lives

Most Big O guides hand you a lookup table. Binary search is logarithmic, merge sort is linearithmic, hash insert is constant amortised. Fine for reference. Useless when the interviewer hands you a function you've never seen.

The interview skill is derivation. Counting the dominant operation as a function of input size. The cleanest way to build that skill is to use Big O on code where you don't already know the answer.

Take a single loop. One pass through n elements does n units of work, so it's O(n). Two nested loops over the same array multiply: outer runs n times, inner runs up to n times, total work is n × n which is O(n²). The inner loop in something like a pair-check usually doesn't run the full n each time. The first outer pass runs the inner n-1 times, the next runs n-2, and so on. The sum is n(n-1)/2, which simplifies to O(n²) because the constant 1/2 and the linear term drop out.

The halving pattern, derived from scratch

Take binary search. It's the cleanest example of how O(log n) actually shows up.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Each loop iteration cuts the search space in half. Start with n elements, one comparison leaves n/2, two leave n/4, three leave n/8. You stop when the space hits 1. The question is: how many times can you halve n before reaching 1?

The answer is log₂(n). An array of a million elements needs at most 20 comparisons. A billion needs at most 30. That's why binary search feels almost instant on large inputs.

The shape generalises. Any loop where the search space shrinks by a constant fraction each step is logarithmic. You'll see the same shape when an index doubles (i *= 2), when a range halves, when a balanced-tree walk descends one level per iteration. The derivation isn't memorised. It's derived from the mechanic.

I keep coming back to this one because it's the easiest place to feel the difference between memorising and deriving. Once you've drawn the halving five or six times on a whiteboard, recognising it in unfamiliar code stops being effortful. The searching lesson on my own site walks through the halving invariant frame by frame, then extends the same derivation to predicate search problems where you're binary searching on an answer space instead of an array. Same mechanic, different surface.

A five-step derivation protocol

The five steps below work on any code, whether you've seen it before or not. They're the steps I use myself when an interviewer drops a function I don't recognise.

Identify the dominant operation. Inside the inner loop, the recursive call, the comparison. Whatever you'd count if you were ticking marks on paper.
Express the iteration count as a function of n. A single loop is n. Nested loops multiply. A halving loop is log n. A recursive call that branches twice and reduces by 1 each level builds a tree of depth n, giving 2ⁿ.
Sum across the levels. Single loop: n × O(1) = O(n). Recursive tree: branching factor b, depth d, total nodes roughly b^d. Multiply by the work per node.
Drop constants and lower-order terms. 3n + 5 becomes O(n). n² + n becomes O(n²). The simplification only matters because the notation is about behaviour at large n, where the highest-order term dominates everything.
Do the same thing for space. Track auxiliary memory. Count call-stack frames in recursion. Count the size of any data structure that grows with input.

The protocol works on hash-map resize, on BFS over a graph, on string concatenation in a loop, on dynamic programming with memoisation. It works on code you've never seen. That's the whole point.

A worked example on recursion

Take naive Fibonacci.

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

The dominant operation is the recursive call. Each call to fib(k) makes two more calls. The call tree branches at every level. Depth is roughly n. Total nodes are roughly 2ⁿ. That's O(2ⁿ), which is why naive Fibonacci is unusably slow even for moderate n.

Adding memoisation collapses the tree to O(n) because each subproblem fib(k) is computed exactly once. The work per subproblem is constant, and there are n of them. Same recursion, different complexity, derived from the same counting.

The space complexity of the naive version is O(n) from the call stack, not O(2ⁿ) from the tree. At any moment, only one root-to-leaf path is on the stack. The branches aren't all simultaneously in memory. Easy mistake to make. Easy to catch if you're explicit about which operations are happening at the same time versus across the whole run.

Space complexity, including the parts that get forgotten

Time complexity gets most of the attention. Space gets asked about often enough that ignoring it loses interview points.

Space complexity measures the additional memory your algorithm uses beyond the input. The input array itself doesn't count toward auxiliary space. Sorting in place is O(1) auxiliary. Copying the array first is O(n) auxiliary for the same sort.

The piece that catches even experienced engineers is the recursive call stack. Every recursive invocation adds a frame. A function that recurses n levels deep uses O(n) stack space, even if it doesn't allocate any explicit data structure.

def sum_recursive(arr, i=0):
    if i == len(arr):
        return 0
    return arr[i] + sum_recursive(arr, i + 1)
    # Time: O(n), Space: O(n) due to call stack

The iterative version of the same logic uses constant space. That's the concrete reason converting recursion to iteration is sometimes worth the extra code.

Common space-complexity traps worth knowing by name:

Forgetting to count the recursive call stack.
Counting the input array size as auxiliary space.
Ignoring that hash maps and sets grow with input.
Missing that repeated string concatenation in a loop creates O(n²) total memory because each new string is a fresh allocation.

Where this shows up in interviews

Interviewers don't ask you to recite that merge sort is O(n log n). They hand you a function and ask you to analyse it, or they ask you to improve a brute-force O(n²) solution to O(n) or O(n log n). Derivation, not recall.

That's where a lot of self-taught preparation falls apart. You can grind hundreds of problems and memorise their complexities. If you haven't drilled the reasoning process of counting operations as a function of input, novel code still feels opaque. Learning science has a name for the right drill here: elaborative interrogation. Asking yourself why each operation contributes the work it does, rather than accepting the labelled answer.

Before Big O is derivable, you read a solution and think that looks fast. After, you look at the same solution and know it's O(n log n) because you can point at the divide step and the merge step independently. You can explain why adding a hash map drops a nested loop from quadratic to linear. You can evaluate code you've never seen and tell the interviewer how it scales.

At that point, Big O stops being a label you apply after the fact. It becomes a tool you reason with.

I wrote a longer version on my own blog that includes amortised analysis (the hash-map resize derivation in particular) and the recursion-tree shortcuts for divide-and-conquer.

What's a problem where the textbook complexity made sense to you only after you traced the work by hand? I'm curious which derivations clicked first for people, and which ones stayed stubborn.

BFS vs DFS: The Invariant Decides, Not Your Preference

Prakhar Srivastava — Fri, 22 May 2026 19:56:26 +0000

Two algorithms visit every node in a graph. Pick whichever you remember and most of the time nothing goes wrong. Then an interview hands you a shortest path problem, you reach for DFS because it's faster to write recursively, and you hand back a path that's valid and twice as long as the optimal one. No error. Just a quietly wrong answer you can't debug with the clock running.

TL;DR: BFS uses a queue and processes nodes in distance order, so the first time it reaches a node, that path is the shortest in an unweighted graph. DFS uses a stack, commits to one branch fully, and naturally exposes cycles, topological order, and connected components. The data structure creates the guarantee. The guarantee decides which problems each one can solve.

The queue and the stack create different guarantees

BFS and DFS aren't two flavors of the same traversal. They hold different invariants, and the invariant is what decides which problems each one can solve.

Breadth first search processes every node at distance 1 from the source before any node at distance 2, every node at distance 2 before distance 3, and so on. It uses a queue to hold that order. You get a level by level sweep outward from the start.

Depth first search drives down one path as far as it goes, then backtracks. It uses a stack, or the call stack when you write it recursively, to remember where it came from. One branch gets fully exhausted before the next one is touched.

That sounds academic until it costs you a problem. The order each one visits in is not a cosmetic difference. It's the whole reason one of them can answer a question the other can't.

Why BFS finds the shortest path and DFS doesn't

The queue is the entire reason BFS works for shortest paths. A queue is first in, first out. When you enqueue the neighbours at distance d, they sit behind any remaining distance d-1 nodes and ahead of every future distance d+1 node. The queue enforces distance order without you ever tracking distance explicitly.

The stack is last in, first out. The most recently pushed node gets processed next, so you keep diving deeper along whichever neighbour you pushed last. DFS might reach a node through a 7 edge path before it ever finds the 2 edge one. BFS can't do that, because it finishes every 2 edge path before it starts any 7 edge path.

I used to reach for whichever traversal I'd practiced most recently. The first time I watched that break a real solution, it was on a grid.

A grid problem where the wrong traversal costs you

Take a 2D grid where 0 is passable and 1 is a wall. You want the minimum number of steps from the top left corner to the bottom right, moving in four directions. Every move costs the same one step, so BFS's distance guarantee applies directly.

from collections import deque

def min_steps(grid):
    rows, cols = len(grid), len(grid[0])
    goal = (rows - 1, cols - 1)
    if grid[0][0] == 1 or grid[goal[0]][goal[1]] == 1:
        return -1

    queue = deque([((0, 0), 0)])
    seen = {(0, 0)}
    while queue:
        (r, c), dist = queue.popleft()
        if (r, c) == goal:
            return dist
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0 and (nr, nc) not in seen:
                seen.add((nr, nc))
                queue.append(((nr, nc), dist + 1))
    return -1

The first time popleft() returns the goal, dist is the shortest distance. Nothing else can reach the goal in fewer steps, because the queue processed all the closer cells first.

Now swap queue.popleft() for a stack pop() and you have DFS. The first time it reaches the goal, the distance could be any valid length, often a wandering one. The code looks almost identical. The guarantee is gone.

The memory trade nobody mentions

The two algorithms also use memory differently, and the graph's shape decides which is cheaper. BFS holds the entire frontier at once. In a balanced tree with branching factor b and depth d, the queue holds O(b^d) nodes at the widest level. DFS holds at most O(d) nodes on the stack, one per level of depth. For a deep, narrow graph, DFS is far lighter. For a shallow, wide one, either works.

DFS also has a recursive form BFS can't match. When you write DFS recursively, the call stack is the stack, so you manage no explicit collection at all. That maps cleanly onto problems that are recursive by nature: trees, nested configurations, expression parsing. BFS has no equivalent, because a queue isn't built into the call stack.

How I decide which one to reach for

The question I ask now is simpler than any rule of thumb: does this problem need a distance guarantee or a structural property? Distance guarantee points at BFS. Structural property, meaning cycles, ordering, or connectivity, points at DFS.

Reach for BFS when the problem needs:

Shortest path: minimum steps in a grid, shortest word transformation, nearest distance to a target, all in an unweighted graph.
Level order processing: anything handled layer by layer, like a binary tree level order traversal or finding every node at distance k.
Nearest match: BFS hits the closest valid node first because it explores in distance order.

Reach for DFS when the problem needs:

Cycle detection: DFS tracks which nodes are currently on the recursion stack, so a back edge to one of them means a cycle.
Topological order: DFS finish times, reversed, give a valid topological ordering for a directed acyclic graph.
Connected components: run DFS from an unvisited node, mark everything reachable, repeat from the next unvisited node.
Path enumeration: backtracking and all source to target paths, because DFS explores one complete path before trying alternatives.

One trap worth naming: BFS assumes every edge costs the same. The moment edges carry weights, its distance order no longer holds, and you need Dijkstra's algorithm, or Bellman-Ford if weights can go negative.

I wrote a longer version on my own blog that traces both algorithms step by step on the same six node graph and walks through a directed cycle detection example with code.

Which graph problem finally made the BFS vs DFS choice obvious for you, the one where picking wrong actually broke your solution rather than just slowing it down?

Backtracking Algorithm Explained: An N-Queens Walkthrough

Prakhar Srivastava — Thu, 21 May 2026 16:03:35 +0000

The textbook line on backtracking is "try everything and undo what doesn't work." Accurate, and useless. It tells you nothing about how to write a solution to a problem you've never seen. Backtracking isn't trial and error. It's a depth first walk over a state space tree with a rule for quitting a branch the moment it can't lead anywhere valid.

Once you see it that way, the trick stops being clever and starts being mechanical. Every backtracking problem you'll meet runs the same loop. The only thing that changes is what you're choosing and what counts as a dead branch.

TL;DR: Backtracking builds a solution one decision at a time and walks a state space tree with DFS. When a partial solution breaks a constraint, you abandon that branch and try the next option. The whole algorithm is choose, check, undo. The variation between problems is what you choose and what the constraints are.

What backtracking actually is

Picture a tree where the root is the empty solution. Each edge is a decision: place a queen in a column, add a character to a string, include an element in a subset. Each node is the partial solution you have so far. Leaves are either complete valid answers or dead ends where a constraint already broke.

Exhaustive search builds every leaf and checks each one after the fact. Backtracking checks on the way down and stops descending the instant a partial answer is doomed. On a board with n queens, exhaustive search inspects all n^n configurations. Backtracking inspects a sliver of that, because it never places a queen in a row where a conflict already exists.

For tiny inputs the difference is academic. Generate every subset of a 10 element array and pruning saves you nothing, there's nothing to prune. The advantage shows up when constraints are tight and the search space is large, which is exactly the shape of the problems interviewers like.

The choose, check, undo skeleton

Strip away the problem specifics and every backtracking routine does three things in a loop:

Choose: extend the current partial solution with one option.
Check: test whether that extension violates a constraint. If it does, don't recurse into it.
Undo: after the recursive call returns, reverse the choice so the next option starts from a clean state.

That last step is the one people forget, and it's the one that quietly produces wrong answers instead of crashes. If you append to a path or flip a visited flag and never reverse it, later branches inherit corrupted state from earlier ones.

Walking N-Queens by hand

N-Queens is the cleanest place to watch this run. Place n queens on an n x n board so none attack each other, no shared row, column, or diagonal. The tree has n levels, one per row, and at each level you pick a column. The branching factor starts at n and shrinks as conflicts knock out columns.

Here's a partial trace for n=4, watching where pruning kicks in:

Row 0: try column 0
  Row 1: column 0 -> PRUNE (same column)
  Row 1: column 1 -> PRUNE (diagonal with row 0)
  Row 1: column 2 -> ok, partial [0, 2]
    Row 2: every column conflicts -> BACKTRACK
  Row 1: column 3 -> ok, partial [0, 3]
    Row 2: column 1 -> ok, partial [0, 3, 1]
      Row 3: every column conflicts -> BACKTRACK
    ...all of row 1's options exhausted -> BACKTRACK
Row 0: try column 1
  Row 1: column 3 -> [1, 3]
    Row 2: column 0 -> [1, 3, 0]
      Row 3: column 2 -> [1, 3, 0, 2] -> SOLUTION

Without pruning you'd evaluate all 4^4 = 256 placements. With it, the algorithm touches roughly 20 nodes before the first solution. Early constraint checks did the heavy lifting. The code is just the skeleton with the constraint filled in:

def solve_n_queens(n):
    solutions = []
    board = []

    def is_valid(row, col):
        for prev_row, prev_col in enumerate(board):
            if prev_col == col:
                return False
            if abs(prev_row - row) == abs(prev_col - col):
                return False
        return True

    def backtrack(row):
        if row == n:
            solutions.append(board[:])
            return
        for col in range(n):
            if is_valid(row, col):
                board.append(col)     # choose
                backtrack(row + 1)    # explore
                board.pop()           # undo

    backtrack(0)
    return solutions

board.append(col) is the choose. is_valid(row, col) is the check that prunes. board.pop() is the undo. The domain looks completely different on Sudoku or word search, but the three pieces are always sitting right there.

The three shapes backtracking takes

Backtracking problems aren't all the same. They sort into three shapes by how much you can prune:

Unconditional enumeration. Produce every arrangement with no extra rule: all subsets, all letter combinations of a phone number. The tree branches at every position and every leaf is valid output. Nothing to prune, you walk the whole tree.
Conditional enumeration. Same branching shape, but a constraint kills branches mid construction: valid parentheses, combinations that sum to a target, permutations of distinct elements. Some branches die before the leaf because the partial answer already broke the rule.
Backtracking search. Find one or more configurations that satisfy a global constraint: N-Queens, Sudoku, maze pathfinding. Pruning is heaviest here because each placement constrains every later one.

The reason this taxonomy is worth memorising: it tells you how aggressive your pruning should be before you write a line. Search problems want constraint checks at every level. Unconditional enumeration wants none, and adding them just slows you down.

To see the same skeleton with no pruning at all, here's generating every subset of an array. Every node is already a valid answer, so there's nothing to check:

def subsets(nums):
    result = []

    def backtrack(start, path):
        result.append(path[:])          # every node is a subset
        for i in range(start, len(nums)):
            path.append(nums[i])        # choose
            backtrack(i + 1, path)      # explore
            path.pop()                  # undo

    backtrack(0, [])
    return result

Same three pieces. The is_valid check from N-Queens is simply absent, because in unconditional enumeration there's no constraint to prune on. Drop the path.pop() line, though, and you reproduce the most common backtracking bug: every subset after the first comes back polluted with elements left over from an earlier branch. The undo is what keeps one mutable list honest across the whole tree.

One more thing the shapes tell you is the cost. The worst case for backtracking is exponential, because the tree can have exponentially many nodes. Pruning doesn't change that worst case, it changes how much of it you actually visit. On loose constraints you walk most of the tree anyway. On tight ones like N-Queens you skip the overwhelming majority, which is why the same algorithm feels fast on one problem and hopeless on another.

When backtracking is the wrong call

Reaching for backtracking on the wrong problem is a common interview misstep. Three signals tell you it fits:

The problem wants all valid configurations, or one valid configuration. "Generate all", "find every", "place the" are tells. If it only wants a count, DP is usually faster.
Each decision constrains future decisions. Placing an element at A removes options at B. That's a constrained search tree.
There's no greedy shortcut and no overlapping subproblem to cache. If locally optimal choices give the global optimum, that's greedy. If the same subproblem repeats, that's DP.

When the input is large and you can't prune hard, even correct backtracking times out. That's the boundary where the interviewer is usually steering you toward dynamic programming.

A quick gut check before you commit: estimate the branching factor and the depth. If the tree is roughly b choices deep d levels and your constraints don't kill many branches, you're looking at something near b^d work. When that number is astronomical and the problem only wants a count or a single optimal value, that's the cue to stop and ask whether the states overlap.

Where backtracking turns into DP

The two are closer than they look. When a backtracking solution explores the same partial state through different decision paths, you're recomputing work. Cache those states and top down DP falls out of the same recursion you already wrote.

That progression, from raw search to memoised recursion to a table, is one of the most reusable moves in interview prep. It also explains why solid recursion has to come first. Backtracking is recursion with a choose, check, undo wrapper, so if the recursive call still feels shaky, the wrapper won't save you. If you want to drill the pattern shapes directly, the backtracking pattern lessons work through each of the three with their own trigger checklist.

The gap that trips most people up isn't writing the recursion. It's trusting the moment a branch should be abandoned, and that's the part I keep coming back to in my own work.

I wrote a longer version on my blog that walks through the other two shapes with full code, plus the common bugs that make backtracking silently return wrong answers.

Which backtracking problem finally made the choose, check, undo loop click for you?

AVL Trees Explained: How Rotations Keep BST Operations O(log n)

Prakhar Srivastava — Wed, 20 May 2026 19:50:04 +0000

You learn binary search trees and walk away believing every operation is O(log n). It isn't. That guarantee only holds when the tree stays balanced, and a plain BST has no mechanism to enforce that. Insert [1, 2, 3, 4, 5] into an empty BST and you've built a linked list with extra steps.

TL;DR: An AVL tree adds one rule to a BST. No node's left and right subtrees can differ in height by more than 1. When an insertion breaks the rule, the tree fixes itself through rotations. Every operation stays O(log n). The four rotation cases aren't four separate things to memorise. They're two atomic moves combined twice.

The balance rule everything else hangs on

An AVL tree is a self balancing BST where, for every node, the heights of its left and right subtrees differ by at most 1. That's the whole rule. Every operation that preserves the rule preserves O(log n).

You track the rule with the balance factor:

balance_factor(node) = height(left_subtree) - height(right_subtree)

A node is balanced when its balance factor is -1, 0, or +1. Zero means both subtrees have the same height. +1 means the left is one level taller. -1 means the right is. When an insertion or deletion pushes any node's balance factor to -2 or +2, the tree is unbalanced and needs fixing.

The fix is always a rotation, and it's always local. You don't rebuild the tree. You rearrange 2 or 3 pointers near the imbalance and the invariant snaps back into place.

This single rule is strict enough to guarantee logarithmic height. An AVL tree with n nodes has height at most about 1.44 log(n). Slightly taller than a perfectly balanced tree, but the difference is a constant factor. Every operation traverses from root to leaf, so when height stays logarithmic, so does runtime.

Why the rule matters more than it looks

A plain BST gives you none of this. Insert the values [1, 2, 3, 4, 5] into an empty BST. Each value is larger than the last, so every insertion goes right. The resulting tree is a straight line, structurally identical to a linked list. Searching for 5 walks all five nodes. O(n), not O(log n).

Sorted input isn't unusual either. Database indices built from timestamped logs, primary keys assigned by an auto-increment column, sensor readings ordered by time. All of these produce sorted insertion sequences. A plain BST degenerates into a linked list on every one of them.

Performance depends entirely on height. Balanced, you get O(log n). Degenerate, you get O(n). Lose control of the height, lose control of the performance. That's the whole reason self balancing exists.

The four rotation cases, and why they're really just two

Every AVL imbalance falls into one of four cases. Each one is resolved by a specific rotation that preserves the BST ordering (left < parent < right) while restoring the height balance.

There are only two atomic moves: a left rotation and a right rotation. The four cases are these two moves applied once or twice.

LL case (left child of a left-heavy node): single right rotation on the unbalanced node
RR case (right child of a right-heavy node): single left rotation on the unbalanced node
LR case (right child of a left-heavy node): left rotate the left child first to straighten the kink, then right rotate the unbalanced node
RL case (left child of a right-heavy node): right rotate the right child first, then left rotate the unbalanced node

The single rotations handle the "outside" imbalances. The double rotations handle the "inside" imbalances where a single rotation would just move the heavy side from one position to another without fixing it. The trick is recognising which side of the parent is heavy AND which side of that child is heavy. Those two answers pick the case.

def right_rotate(z):
    y = z.left
    T3 = y.right
    y.right = z
    z.left = T3
    z.height = 1 + max(height(z.left), height(z.right))
    y.height = 1 + max(height(y.left), height(y.right))
    return y

Notice what the rotation actually does. It moves 3 pointers and updates 2 heights. That's it. Constant time. The O(log n) part of an insertion comes from walking down the tree to find the insertion point and walking back up to check balance factors. The rotation itself is free by comparison.

Tracing an insertion sequence

Walk through inserting [3, 2, 1, 4, 5] into an empty AVL tree. I find that watching two different rotations fire in the same sequence is what makes the four-case table click.

Inserting 3 creates a single-node tree with balance factor 0.

Inserting 2 sends it left of 3. Node 3's balance factor is +1 (left subtree height 1, right subtree height 0). Still within the rule.

Inserting 1 triggers the first rotation. 1 goes left of node 2. Walking back up, node 2's balance factor is +1 and node 3's is +2. That's an LL case (node 3 is left-heavy, its left child 2 is also left-heavy). A right rotation on node 3 puts node 2 at the root, node 1 on the left, and node 3 on the right. All balance factors drop to 0.

Inserting 4 goes right from node 2 to node 3, then right again to become node 3's right child. Walking back, node 3's balance factor is -1, node 2's is 0. Within the rule.

Inserting 5 breaks balance again. It lands as node 4's right child. Walking back up, node 4's balance factor is -1, but node 3's hits -2. That's an RR case. A left rotation on node 3 moves node 4 into node 3's position, with node 3 as 4's left child and node 5 as 4's right child. All balance factors back to 0.

Final tree: node 2 at the root, node 1 on the left, node 4 on the right, with 3 and 5 as 4's children. Height is 2.

A plain BST with the same insertion order [3, 2, 1, 4, 5] wouldn't degenerate this badly. But try [1, 2, 3, 4, 5] and the plain BST becomes a linked list of height 4. The AVL version still has height 2.

The full insertion algorithm bundles the BST insert with the balance check on the way back up:

def insert(node, key):
    if not node:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)

    node.height = 1 + max(height(node.left), height(node.right))
    bf = balance_factor(node)

    if bf > 1 and key < node.left.key:
        return right_rotate(node)
    if bf < -1 and key > node.right.key:
        return left_rotate(node)
    if bf > 1 and key > node.left.key:
        node.left = left_rotate(node.left)
        return right_rotate(node)
    if bf < -1 and key < node.right.key:
        node.right = right_rotate(node.right)
        return left_rotate(node)

    return node

After every insertion you only check balance factors along the path from the inserted node back to the root. At most one rotation (single or double) is needed.

Why deletion is harder than insertion

This is the part most beginner tutorials gloss over and the part interviewers like to probe.

Insertion can break balance at one node along the ancestor path. You rotate once and you're done. Deletion isn't that clean.

When you remove a node, the height reduction can propagate upward. Fixing the first imbalanced ancestor might shorten that subtree, which then unbalances the next ancestor up. In the worst case you'll rotate at every level from the deleted node's position back to the root. That's O(log n) rotations instead of the single rotation insertion needs.

The rotation selection logic stays the same. You still compute balance_factor(node) and check whether the imbalance is LL, RR, LR, or RL. The difference is that you can't stop after the first fix. You have to keep walking up.

There's also a subtlety with the node you're actually removing. If the target has two children, you replace it with its in-order successor (smallest in the right subtree) or its in-order predecessor (largest in the left subtree), then delete that node instead. The replacement is identical to plain BST deletion. The AVL-specific work starts afterward, during the upward balance check.

I'd argue most interview questions won't ask you to implement AVL deletion from scratch. But understanding why deletion is more expensive than insertion is what separates "I've memorised the four cases" from "I've actually thought about the invariant." If an interviewer asks about the tradeoff of stricter balance, deletion cost is the concrete answer.

When to reach for AVL vs Red-Black

In interviews, AVL trees show up two ways: explaining self balancing BSTs conceptually, and implementing balanced insertion from scratch. Red-Black trees show up as a "why don't standard libraries use AVL" question.

Plain BST. Fine when input is random or the problem doesn't require worst-case guarantees. Tree problems on LeetCode typically assume balanced input and don't ask you to maintain balance yourself.

Red-Black tree. Relaxes the balance constraint to height up to 2 log(n) in exchange for cheaper insertion and deletion. At most 2 rotations per operation, vs potentially O(log n) for AVL deletion. Java's TreeMap, C++'s std::map, and Linux's CFS process scheduler all use Red-Black trees. So does the Linux kernel's anonymous VMA tree. Most standard libraries do.

AVL tree. Enforces stricter balance. Maximum height about 1.44 log(n) versus about 2 log(n) for Red-Black. Lookups are faster because the tree is shorter. The tradeoff is that insertions and deletions are slower because AVL trees may need more rotations to maintain the stricter rule.

Why are AVL trees less common in production despite being older and simpler? Looser balance makes insertion-heavy workloads faster, and most real systems insert and delete more than they search-only.

For interviews though, AVL trees are the better answer. The rotation logic is more intuitive than Red-Black's five-case colour rules. If an interviewer asks you to implement a self balancing BST from scratch, AVL is the cleaner choice under time pressure. I keep seeing candidates wedge themselves into Red-Black trees and run out of time at the recolouring step. AVL trees let you spend that same time tracing the four cases instead.

Honest credit where it's due: Red-Black trees aren't "worse." They're optimised for a different workload. The standard library authors knew exactly what they were trading. It's the same engineering call you'd make if you were building a key-value store that inserts billions of times a day. AVL is the wrong choice there. It's only the right choice for read-heavy workloads, or for an interview where the simpler invariant lets you finish before the timer.

The three mistakes that cost candidates in interviews

These are the patterns I keep seeing on AVL questions, in roughly the order they show up.

Stale heights after rotation. You rotate nodes y and z but forget to recalculate their height fields. The next balance factor check uses stale data and every decision downstream is wrong from that point on.
Top-down balance checking. You insert at a leaf and trace upward to find the first unbalanced ancestor. Starting from the root downward misses the actual imbalance point or applies a rotation at the wrong node.
Misidentified LR / RL cases. Under pressure it's tempting to see a left-heavy node and immediately right rotate. If the left child is right-heavy, a single right rotation makes things worse. Sketching the three nodes on paper before choosing the rotation takes five seconds and avoids a cascading error that's painful to debug mid-interview.

Codeintuition's Binary Search Tree course walks the balance invariant from first principles. If the four-case table still feels like four separate things to memorise, the BST course traces balance factor computation across multiple tree shapes before any rotation code appears.

I wrote a longer version on my blog that walks deletion with the upward rebalance loop and includes the AVL vs Red-Black tradeoff matrix.

Which AVL rotation case took the longest to internalise for you, and what was the problem or sketch that finally made it click?

I Mapped 450+ FAANG Problems: Amazon, Google, and Meta Don't Test the Same DSA Patterns

Prakhar Srivastava — Tue, 12 May 2026 15:23:46 +0000

The most common DSA prep mistake I see at the FAANG band isn't undertraining or overtraining. It's training as if Amazon, Google, and Meta all sample from the same pattern bag. They don't. After mapping company tags across 450+ handpicked interview problems, the gap between Amazon's pattern footprint and Google's is larger than most candidates expect, and materially changes how prep time should be allocated.

TL;DR: Amazon spans 11+ distinct DSA pattern families, the broadest of any major company. Google has narrower coverage but a distinctive emphasis on predicate search (binary search on the answer space, not on a sorted array). Seven patterns appear at six or more companies and form the universal baseline that every FAANG candidate has to own before specialising.

The seven patterns every FAANG round assumes you can run

Before company specific differences matter, there's a universal baseline. Seven patterns appear at six or more major companies in the data set. Skipping any of them, regardless of target company, is a structural error in the prep plan.

Company-specific prep matters. But only after the universal baseline is genuinely automatic.

The most heavily tagged is LRU Cache, at 19 companies. That's every FAANG member, plus DoorDash, Oracle, Zoom, PayPal, Twilio, TikTok, eBay, Yandex, LinkedIn, Zillow, Intuit, and Cloudera. The reason it spreads that far is structural: a single problem tests hash table mechanics, doubly linked list manipulation, and design composition at once. No alternative problem covers the same combination at the same difficulty.

The remaining six universal patterns:

Counting (hash table): 9 companies. Frequency counts, anagram grouping, character buckets. Most broadly tested hash table pattern.
Backtracking: 8 companies. Generate parentheses through N-Queens. Tests recursive state and pruning.
Prefix Sum: 8 companies. Range queries, subarray sums, equilibrium problems. Almost always undertaught relative to its testing rate.
Binary Search: 7 companies. The classic sorted array variant. Includes rotated array and boundary problems.
Fixed Sliding Window: 7 companies. Window of fixed size with frequency tracking inside it.
Variable Sliding Window: 6 companies. Different triggers from fixed: a contracting mechanism that has to fire on a condition, not on a counter.

Prefix Sum is the one that gets shortchanged most. Eight companies tag it. Most prep plans treat it as a footnote because it doesn't have a flagship problem the way LRU Cache or Two Sum do. That's a mismatch worth correcting: it gives disproportionate company coverage relative to the time required to learn it well.

The highest ROI interview patterns are often the ones without famous flagship problems.

Predicate search: the pattern Google tests that nobody calls by name

Google shares the universals, but the pattern that distinguishes Google interviews from the rest is predicate search. This is binary search applied not to a sorted array but to the answer space itself. You define a range of possible answers, then binary search that range by checking feasibility at each midpoint.

The classic shape is the minimum ship capacity problem. You're given package weights and D days. Find the smallest ship capacity that lets you ship everything in D days.

Instead of trying every capacity from 1 upward, you frame the search range:

Low: the heaviest single package (you have to lift it on day one)
High: the sum of all weights (one giant day)

Then binary search inside that range:

def min_ship_capacity(weights, days):
    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        day_count, current_load = 1, 0
        for w in weights:
            if current_load + w > mid:
                day_count += 1
                current_load = 0
            current_load += w
        if day_count <= days:
            hi = mid
        else:
            lo = mid + 1
    return lo

The mechanical shift from classic binary search is small, but the mental shift is large. In classic binary search, the search space is given to you (a sorted array). In predicate search, you construct the search space from the constraints, then run binary search on your own abstraction. You're searching for the minimum value that satisfies a feasibility predicate, not a value already sitting somewhere in the input.

LeetCode tags these problems "Binary Search" alongside sorted array problems. The tag isn't wrong, but it hides the model shift. If your only model for binary search is "find a value in a sorted array," predicate search will freeze you because the starting assumption doesn't match. Google asks predicate search variants more than any other company in the data set: punctual arrival speed, trip completion frenzy, calculate square root, capacity to ship within D days, all the same shape.

Most candidates know binary search on arrays. Far fewer recognise when the answer itself is the search space.

A useful test before practising binary search problems: can you state, in one sentence, what the search range is and what the feasibility check is? If yes, you're doing predicate search. If you reach for mid = (left + right) // 2 without that explicit framing, you're guessing.

Why Amazon's pattern coverage is wider than anyone else's

Amazon's problem set covers Counting, Fixed and Variable Sliding Window, Prefix Sum, LRU Cache, Randomised Set, Binary Search, 2D Binary Search, Staircase Search, Maximum Predicate Search, Queue Design, and Backtracking. That's 11+ pattern families against Google's 7-8 and Meta's 6-7.

The practical effect on prep is concrete. A Google candidate who goes deep on predicate search, counting, and graphs covers a meaningful slice of what they'll actually see. An Amazon candidate who goes equally deep on three families has blind spots across the other eight. The "study three patterns deeply and hope you land in your zone" strategy has a lower hit rate at Amazon than anywhere else.

The Bar Raiser round amplifies the breadth requirement. The Bar Raiser is an interviewer pulled from outside the hiring team, with veto power, and they're not bound to the team's domain. They can sample any pattern family Amazon tests. If the round happens to land on a category you skipped, the heuristic of "the team usually asks X" doesn't catch you.

Going deep still matters. But at Amazon the breadth axis carries more weight than at the narrower companies, and the prep allocation should reflect that.

Meta, Microsoft, Apple: where the rest of the picture sits

Meta concentrates on Sliding Window (both Fixed and Variable), Prefix Sum, Counting, and design problems (LRU Cache, Randomised Set). Maximum Predicate Search shows up too. Compared to Google, Meta places less weight on searching variants and more on hash table depth and design implementation. If Amazon tests breadth and Google tests reasoning depth, Meta wants hash table fluency in a tighter band.

Microsoft is distinct for 2D Binary Search and Staircase Search. These are multi dimensional search problems where the input is a sorted matrix and the search has to respect both axes. Most prep plans skip them entirely because they don't appear at Google or Meta. If Microsoft is your target, weight 2D search higher and variable sliding window lower.

Apple tilts toward fundamentals tested deeply. Five Counting problems carry Apple tags, alongside Binary Search, Prefix Sum, and Backtracking. Apple's data signals a preference for candidates with strong basics over candidates with broad pattern coverage. The advanced design problems (Randomised Set, Queue Design) that Amazon tests don't appear in Apple's tags.

What a company doesn't test matters as much as what it does. Every hour spent on patterns your target company doesn't emphasise is an hour that could've gone to one they do. Google shows minimal tags for Queue Design and 2D Binary Search. Meta shows lower coverage of searching variants. Microsoft shows fewer tags for Variable Sliding Window. Apple barely tests advanced design at all. If you're prep-allocated against the wrong company's profile, you're optimising the wrong axis.

Allocating prep time once you know your target

Three rules fall out of the data, in this order:

Cover the universals first, regardless of target. LRU Cache, Counting, Backtracking, Prefix Sum, Binary Search, Fixed Sliding Window, Variable Sliding Window. Skip none of them.
Specialise second. Predicate search for Google. Design breadth and Bar Raiser follow up depth for Amazon. Design depth and sliding window fluency for Meta. 2D and staircase search for Microsoft. Counting and fundamentals depth for Apple.
Cut what doesn't match. Targeting Google and not Amazon? Queue Design can wait. Targeting Meta and not Microsoft? Staircase Search can wait. Prep time is finite.

Two patterns are worth flagging again. Prefix Sum is undertaught relative to its 8-company tag count. Almost no popular prep plan gives it the time it deserves. And LRU Cache is the one problem you genuinely shouldn't walk into any FAANG round without being able to write cold, including the doubly linked list helpers. Nineteen company tags, no exceptions.

Most prep platforms organise problems by data structure (Hash Table, Tree, Graph), which buries the company-level signal entirely. The more useful filter is patterns by company tags. Once you can answer "which 6-8 patterns has my target company asked across 450+ problems," the allocation question gets concrete and fast.

I wrote a longer version with the per company breakdown and the FAQ on my own blog covering the patterns each company genuinely deemphasises (Google's quiet skip on Queue Design, Apple's near absence of advanced design).

If you've interviewed at more than one of these five companies, which pattern came up that you weren't expecting based on the company's reputation?

The Amazon Bar Raiser Isn't Testing Your Solution. It's Testing the Follow Up.

Prakhar Srivastava — Mon, 11 May 2026 14:32:57 +0000

You're 15 minutes into an Amazon coding round. You've identified the pattern, your solution handles the examples, you're about to submit. Then the interviewer changes a constraint. Sorted input is now unsorted. The complexity ceiling drops from O(n log n) to O(n). Your original solution collapses, and the rest of the round is now about whether you can reconstruct the approach from the invariant rather than from memory.

That moment, the constraint shift after the working solution, is where the Bar Raiser's evaluation lives. Most prep treats it as a bonus question. The Bar Raiser treats it as the round.

TL;DR: Amazon's Bar Raiser is an independent interviewer with veto power who tests the same problems as a regular round but probes the follow up much harder. Two things make Amazon prep different from Google or Meta prep: the pattern coverage is broader (eleven plus pattern families vs. six or seven), and the round's evaluation centres on whether you can adapt your solution after a constraint changes, not on whether you can produce the optimal solution first.

What the Bar Raiser is, in one paragraph

Amazon's Bar Raiser is an interviewer pulled from outside the hiring team. Their job is to evaluate the candidate against Amazon's company wide hiring bar, independent of how badly the team wants to fill the seat. They can veto a hire that everyone else approved. They can also push a borderline candidate over the line if they see genuine depth.

In practice, you don't know which of your interviewers is the Bar Raiser. Amazon keeps that ambiguous through the loop. What you do know is that at least one round will be a Bar Raiser round, and that round usually includes a coding problem.

The problem itself looks the same as any other Amazon technical screen. The difference is what happens after you produce a working answer. A standard interviewer often moves on once you've solved it. A Bar Raiser keeps going. They'll change a constraint, ask you to optimise, ask why your solution is correct (not just whether it works), or walk you through the failure case you didn't test.

The initial solution gets you to the conversation. The follow up is the conversation.

The solution gets you into the round. The adaptation decides the round.

Why Amazon's pattern coverage is wider

Every FAANG company has favourite pattern categories. Google leans heavily on predicate search (binary search on the answer space). Meta concentrates on sliding window and design. Amazon doesn't have a tight central focus the way those two do. Its problem set spans counting, fixed and variable sliding window, prefix sum, LRU style design, randomised set design, binary search and its 2D / staircase variants, queue design, and backtracking.

That's eleven plus pattern families versus roughly seven or eight for Google and six or seven for Meta.

What this means for prep is concrete: the strategy of going deep on two or three pattern families and hoping the round lands in your zone has a lower hit rate at Amazon. A Google candidate who deeply understands predicate search, counting, and graphs covers a meaningful fraction of what they'll see. An Amazon candidate who goes equally deep on three families has blind spots across the other eight.

The Bar Raiser amplifies this. Because they're not bound to the hiring team's domain, they can pull a problem from any of those families. If the round happens to land on a category you skipped, the safety net of "the team usually asks X" doesn't catch you.

The broader your pattern coverage, the smaller the chance any single Bar Raiser pick puts you in unfamiliar territory. Going deep matters too, but at Amazon the breadth axis carries more weight than at the narrower companies.

What the follow up is testing

The interviewer isn't asking the follow up to be cruel. They're testing whether you understood the mechanism of your solution or just the solution itself. If your initial answer was a recalled template for the problem, the constraint change exposes that. If your initial answer was constructed from an invariant, the constraint change is something you can adapt to.

Strong candidates optimise from understanding. Weak candidates optimise from memory.

A worked example makes this concrete. LRU Cache is one of Amazon's most reliably tested problems. The standard solution composes a hash map (O(1) key lookup) with a doubly linked list (O(1) insert and removal at any node when you have the node reference). The hash map maps key to list node. Operations look like:

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.map = {}                     # key -> ListNode
        self.head = ListNode()            # most recently used end
        self.tail = ListNode()            # least recently used end
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._add_to_front(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.map:
            self._remove(self.map[key])
        node = ListNode(key, value)
        self._add_to_front(node)
        self.map[key] = node
        if len(self.map) > self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]

That's the answer the Bar Raiser expects you to land. Now the follow up: each entry has a TTL. Reads on an expired entry must return -1. The cache must still operate at expected O(1) per call.

The candidate who memorised LRU starts redesigning from zero. The candidate who built it from the invariant asks one question first: which invariant did the doubly linked list maintain, and does that invariant still hold under TTL?

The list maintained an ordering invariant: nodes near the head were used more recently than nodes near the tail. Eviction removed the tail because tail was the least recently used. With TTL, the eviction criterion changes from "least recently used" to "expired or least recently used." The list ordering by recency is still useful for the second clause, but the first clause needs a different signal. Two choices land:

Lazy expiry: on get, if the node's expiry timestamp has passed, treat it as a miss, remove the node, return -1. On put, when the cache is full, evict the tail as before. Simple, keeps the data structure unchanged. Worst case has expired entries lingering until they're touched.
Eager expiry: maintain a second ordered structure keyed by expiry time (a min heap or a second linked list ordered by expiry). On every get or put, sweep expired entries off the front of the expiry structure. More memory, tighter behaviour on memory pressure.

The Bar Raiser doesn't necessarily care which one you pick. They care whether you can articulate which invariant you're preserving and which one you're modifying. The candidate who answers "the recency ordering still holds, I'm adding an eviction predicate that checks expiry first" has demonstrated something about reasoning that solving twenty more problems wouldn't have.

The three signals the round is graded on

Three threads run through what separates a "hire" rating from a "no hire" in a Bar Raiser coding round, and they correspond to the three places the round lives.

Clean reasoning under loose constraints. The problem statement is often deliberately under specified. Inputs might or might not be sorted. Sizes might be zero. Negative numbers might appear. The candidate who immediately asks the clarifying questions, defines assumptions on a whiteboard area, and only then starts coding signals the kind of structured thinking Amazon values. Jumping into code without defining the problem space reads as someone operating from pattern memory rather than from understanding.

Adaptation across the follow up. This is the LRU + TTL example above. The follow up isn't a new problem. It's the same problem with a constraint flipped. The candidate who can isolate which part of the previous solution depended on the changed constraint passes. The candidate who scraps and restarts shows that the previous solution was lookup, not construction.

The follow-up is usually testing whether your first solution was constructed or recalled.

Articulation of why. Bar Raisers listen for the explanation that goes past "I'm using a hash map here." They want to hear what invariant the hash map maintains, what would break with an array, what tradeoff you accepted. A candidate who can talk through the load bearing reasoning is a candidate who would raise the team's average performance, which is the literal evaluation Amazon writes down.

The four mistakes the round punishes

These are not coding mistakes. They're prep mistakes that compound under the format.

Solving silently. You finish in fifteen minutes and present the answer. The Bar Raiser has nothing to evaluate beyond the output. Your reasoning made no observable trace. Narrate the structural choices as you go: why a hash map and not a sorted array, why an O(n) first pass instead of trying for O(log n), what edge case you'll come back to. The round is graded on observable reasoning, not just output.
Chasing the optimal solution before the working one. Some candidates spend twenty minutes thinking before writing a line, hunting for the optimal solution out of the gate. Then the follow up arrives at minute thirty five and there's no time for it. Get a correct O(n^2) or O(n log n) working first, confirm edge cases, then improve when the Bar Raiser asks. The follow up is part of the round's grade. Running out of time on it is a soft fail you didn't have to take.
Treating the follow up as a new problem. When the constraint changes, the instinct is to discard the previous solution and start fresh. That's almost always wrong. The follow up is testing whether you understand the structural relationship between the constraint and your approach. Ask which part of your solution depended on the constraint that just changed, then modify only that part. If the original used binary search because the input was sorted and the follow up removes the sort guarantee, you change the search mechanism, not the algorithm.
Skipping edge cases until prompted. Empty input, single element, duplicate values, integer overflow boundaries. Walking through two of these unprompted before the interviewer asks signals thoroughness and pre empts the follow up that targets the case you skipped. Reactive edge case handling reads as a candidate who optimises for the example and not for the input space.

What this changes about how to prep

The standard FAANG prep approach is to go deep on two or three pattern families and hope the interview lands in their zone. That works at companies with narrower coverage. For Amazon's breadth it leaves too many uncovered surfaces, and for the Bar Raiser in particular it leaves you with no recovery path if the chosen pattern isn't one you went deep on.

Two adjustments help.

The first is interleaving over blocking. Block practice is a week on sliding window, a week on dynamic programming, a week on graphs. Interleaved practice rotates between pattern families inside the same study session. Cognitive science research on interleaved practice consistently shows that mixing problem types during study improves your ability to identify which pattern applies to a new problem. Mixed practice is harder while you're doing it (you can't lean on the priming of "this week is sliding window, every problem is sliding window") and that's the point. The harder identification work during practice is the same identification work the Bar Raiser's follow up will require.

The second is practising the follow up explicitly. After every problem you solve, ask: what's the constraint change that would invalidate this solution most? Implement the modified version. The constraint change is the rep that builds the adaptation skill, and adaptation is what the Bar Raiser scores. If LRU Cache is the practice problem, "add TTL" is the rep. If sliding window with at most K distinct characters is the problem, "K varies based on the substring contents" is the rep.

You can do both of these without any platform: a pattern list, a notebook of constraint flips per problem, and a habit of running the second pass before moving on. The reason most prep skips it is that there's no immediate signal it's working. The signal arrives in the round when the Bar Raiser shifts a constraint and you reach for the invariant instead of the template.

If you're preparing for Amazon and your practice still stops after finding the optimal solution, you're missing the part the Bar Raiser actually evaluates.

I wrote a longer breakdown covering:

Amazon's highest frequency pattern families
how the Bar Raiser evaluates coding rounds
and the follow up drills that build adaptation under constraint shifts

Full breakdown here

The day of the loop

A few logistical things candidates often get wrong, worth noting because they're outside your technical preparation but inside the Bar Raiser's evaluation surface.

The onsite loop is typically four or five rounds across a single day or consecutive virtual sessions. One is system design for senior candidates. Two or three are coding rounds. One is behavioural, focused on the Leadership Principles. The Bar Raiser participates in at least one of these, and you won't know which until after the process ends.

Coding rounds are about forty five minutes. Five to ten minutes go to introductions and the problem statement. Twenty five to thirty minutes go to the initial solution. The last ten to fifteen are where the follow up happens. If your first solution takes thirty five minutes because you were reaching for the optimal answer from the start, you've already lost the follow up window.

Each round is evaluated independently. A weak round one doesn't doom you if rounds two and three are strong, and the Bar Raiser considers performance across the loop. Don't mentally rehearse what just happened in the breaks. Reset and walk into the next round.

The debrief happens without you. All interviewers, including the Bar Raiser, meet afterward. If the hiring manager wants to extend an offer and the Bar Raiser objects, the Bar Raiser's veto stands.

Three months from now

The Bar Raiser round isn't a fundamentally different format. It's the same problem solving test with a higher evaluation standard and broader pattern coverage. Two things move the needle for it: pattern breadth across families that gets exercised by interleaved practice, and the ability to adapt your solution when the constraint shifts in the follow up.

I wrote a longer version with the full pattern breakdown across Amazon's tested families on my own blog, including how the loop's other rounds factor into the Bar Raiser's overall judgement.

What's a follow up question from a real interview that changed how you think about the problem itself, not just the solution?

Arrays vs Linked Lists: Why Big-O Alone Doesn't Explain the Tradeoff

Prakhar Srivastava — Sun, 10 May 2026 10:58:45 +0000

The complexity table for arrays and linked lists is the most memorised, least understood reference in interview prep. Arrays give O(1) access. Linked lists give O(1) insertion. That's the answer on every flashcard. The table doesn't lie. It's incomplete. The missing piece, once you have it, makes every entry in that table feel obvious.

TL;DR:

Arrays and linked lists differ for one reason: contiguous memory vs scattered memory.

Every entry in the complexity table follows from that single fact.

Two O(n) operations aren't equal in practice. A million element array scan can often run an order of magnitude faster than the equivalent linked list traversal because of cache locality.

Linked lists win when your algorithm already holds a pointer to the mutation point. They lose when you have to traverse to find it first.

The right question on any problem isn't "which has better Big-O?" It's "which operation does this algorithm perform most?"

What the table tells you, and where it stops

The standard table has six or seven rows: access by index, search, insert at start, insert at end, insert at known position, delete at known position, memory overhead. Each row has two cells. Most engineers memorise the cells and stop there.

The table is correct. Arrays really do give you O(1) index access. Linked lists really do give you O(1) insertion at a known node. The cells aren't wrong. They describe outcomes without explaining why those outcomes happen, which means you can't generalise to a problem you haven't seen.

Memorising complexity tables teaches conclusions. Understanding memory layout teaches reasoning.

If your interviewer asks "which would you use here?" on an unfamiliar problem, a memorised table doesn't help. You need the mechanism underneath.

Memory layout is the root cause

Both data structures store the same thing: a sequence of values. They differ in exactly one way: where those values live.

An array is a single block of contiguous memory. Element 0 sits at the base address. Element 1 sits at base + element_size. Element i sits at base + (i * element_size). The address of any element is a single arithmetic expression. That arithmetic is what makes index access O(1). It's also what makes insertion in the middle O(n): to make room at index 2 of a 5 element array, every element from index 2 onward has to shift right.

A linked list is a chain of nodes that can live anywhere in memory. Node 0 might be at address 1000. Node 1 at address 7500. Node 2 at address 3200. The only way to find node 2 is to start at node 0 and follow the next pointers. That traversal is what makes index access O(n). It's also why insertion at a known node is O(1): you allocate a new node, point it at the next node, and update the previous node's pointer. Two pointer assignments. No shifting.

Every entry in the complexity table is a consequence of these two facts. The math gives you the cells. The layout tells you why.

When the same Big-O isn't the same: cache locality

This is what the table can't show. Both arrays and linked lists are technically O(n) for a full traversal. In practice, an array traversal of a million integers can often run an order of magnitude faster than the equivalent linked list traversal. Same Big-O. Very different wall clock time.

The reason is the CPU cache.

When the CPU reads element 0 from an array, it doesn't fetch just that one integer. It loads an entire cache line, typically 64 bytes, into the L1 cache. For a 4 byte integer array, that single fetch pulls in the next 15 elements alongside arr[0]. Iterating through them costs nanoseconds per access because they're already on chip. The CPU prefetcher notices the access pattern and starts loading the next cache line before you ask for it.

Linked list nodes are scattered across the heap. Each node.next dereference points at an unrelated address. Each pointer chase is a potential cache miss, and a cache miss is roughly a 100 nanosecond round trip to main memory. Multiply that by a million nodes and the gap is enormous.

# Both loops are O(n). The constants differ by ~10x in practice.

# Array: cache friendly contiguous reads
total = 0
for x in arr:
    # next 15 ints already in L1 after the first read
    total += x          

# Linked list: cache hostile pointer chases
total = 0
node = head
while node:
    total += node.value

    # node.next probably triggers a cache miss
    node = node.next

I keep noticing this is what surprises engineers most when they first see it. They've quoted O(n) for traversal in both cases for years. The constant factor never came up because Big-O hides it.

This is the reason ArrayList in Java and Python's built in list are array backed. You're paying the occasional O(n) resize cost in exchange for cache friendly iteration on every operation between resizes. That trade is almost always worth it on real workloads, even ones that involve frequent appends.

If you mention this in an interview, you've shown that you understand the hardware level, not just the math. Two candidates can both quote O(n) for traversal. Only one knows that one of those O(n)s is dramatically slower in practice.

Big-O tells you how growth behaves. Hardware tells you what actually feels fast.

When linked lists actually win

Honest credit where it's due: linked lists are the right structure in a narrow set of cases. Don't read the cache argument as "always pick arrays."

Mutation at a known position: if your algorithm already holds a pointer to the node where you're inserting or deleting, linked lists are O(1) and arrays are O(n). The keyword is "already holds." The standard LeetCode example is LRU Cache, where a hash map gives you O(1) access to the relevant node and a doubly linked list gives you O(1) reordering on every access. Neither structure alone solves the problem.
Pointer only manipulation: reversing a segment, splitting a list at a node, merging two sorted sequences. None of these require moving data, they're pure pointer reassignment. The singly linked list course on my own site covers seven distinct patterns built on this property.
No reallocation cost: dynamic arrays double their capacity when full, which involves copying every element. Linked lists grow one node at a time. For genuinely unbounded streaming workloads with random insertion, the linked list's amortised cost can come out ahead.

The most frequent mistake I watch beginners make is reaching for a linked list the moment they see "insert" or "delete" in a problem, without checking whether they already hold a pointer to the position. Without that pointer, you traverse first (O(n)) and then insert (O(1)). The traversal eats the advantage. Total cost is O(n), same as the array shift, with worse constants because of cache misses.

An O(1) operation that requires O(n) setup is still O(n).

How to choose without memorising the table

Once memory layout is your mental model, the choice becomes a small set of questions you can ask on any problem:

Does the algorithm need random access by index, or binary search? Pick an array. Linked lists can't do O(log n) binary search because finding the middle requires traversal.
Does the algorithm scan the whole structure repeatedly, where speed matters? Pick an array. Cache locality is doing real work in your favour.
Does the algorithm hold direct pointers to nodes it mutates (head, tail, hash map mapped)? A linked list might genuinely win.
Does the algorithm reverse, split, or merge segments by relinking? Linked lists are the natural fit.
Does the algorithm need both random access and frequent reordering at known positions? You probably want both: a hash map of keys to linked list nodes. LRU Cache is the canonical example.

Almost every interview problem involving a sequence of mutations is either an array problem (because access dominates) or a hash map plus linked list problem (because both operations matter). Pure linked list only problems are surprisingly rare in interview banks. They mostly show up when the problem itself is testing whether you can do pointer manipulation cleanly.

An aside on the table itself: the complexity tables you see everywhere aren't useless, even if they're incomplete. They're a fast lookup once you know what's underneath. The point isn't to throw the table out. It's to stop treating it as the answer when it's the symptom.

If Big-O tables still feel like facts you memorise rather than intuitions you can derive, I wrote a longer breakdown covering:

stacks and queues from the same memory model
adjacency lists vs matrices
and why some O(n) operations feel dramatically faster in practice

Full breakdown here

What's a problem where you reached for a linked list and only realised mid implementation that an array would have been cleaner?

Am I Ready for FAANG? A Better Test Than Solving More LeetCode

Prakhar Srivastava — Sat, 09 May 2026 12:40:03 +0000

You've solved 200 problems. Mediums you've already seen take fifteen minutes. The next one you haven't seen freezes you cold inside of five. And every time you ask yourself if you're ready for a FAANG loop, the honest answer is "I don't know."

The "I don't know" isn't a feeling problem. It's that you've been asking a feelings question about a performance outcome.

TL;DR

Self assessed readiness is unreliable because confidence swings with every session.

Solving a familiar problem and constructing a solution to a novel one are different skills.

The fix is a measurable test: an unseen medium in a pattern family you've studied, under timed conditions, with a hard cap on execution attempts.

Pass three of those across three different families and you likely have the level of transfer real interviews actually reward. Fail one and you know exactly where to work.

The signal isn't the count. It's whether the recognition holds when the problem name is hidden.

Why "do I feel ready" is the wrong question

Solving a problem you've seen before and reasoning your way through one you haven't are different skills. Practice on the same patterns repeatedly builds recognition. Recognition only fires on shapes you've encountered. The interview gives you a shape you haven't, and asks you to construct the approach from the constraints alone.

That's the gap between near transfer and far transfer. Near transfer is what 300 problems will buy you, applying what you've practised to similar setups. Far transfer is what FAANG selects for, applying what you've understood to genuinely new ones.

There's a second issue with self assessed confidence. It swings with your last session. Crush five tree problems on Saturday morning and you feel ready. Freeze on an unfamiliar graph problem on Saturday afternoon and the confidence evaporates. Neither data point reflects your stable ability across the families an interview actually draws from.

The result is a loop. You prep, you feel uncertain, you prep more, you still feel uncertain. The method of evaluation is wrong. You're asking a feelings question about a performance outcome.

Interview readiness isn't confidence. It's repeatable performance under unfamiliar conditions.

The three pattern family test

Readiness is a performance threshold you can measure. The protocol takes about two hours and produces a binary answer.

Pick an unseen medium from a family you've studied. Sliding window, tree traversal, graph BFS, DP subsequence. The problem has to be genuinely novel. You haven't solved it, browsed its discussion thread, or read hints for it.
Solve it under real interview constraints. Twenty minute timer. The problem name covered or aliased so you can't reverse engineer the family from the title. No hints. A hard cap on code execution attempts so you can't trial and error your way through. You have to identify the approach, build it, and trace it before running code.
Repeat across two more families you've studied but haven't over practised. One pass isn't signal. Three passes across different families confirms the readiness is broad, not narrow.

Pass means: solve within twenty minutes with fewer than two failed execution attempts. Anything else is useful data.

If you pass three across different families and you likely have the level of transfer real interviews actually reward. If you fail one, you know precisely where to work.

What that looks like on graph BFS

Pick the worst case for this exercise: a medium graph BFS problem you haven't seen. The constraints describe a grid, an adjacency list, or some traversal where shortest distance is the answer.

Two minutes in, you've identified the family. Not from the problem title because that's hidden. From the constraints: shortest distance, unweighted edges, layered exploration. That recognition came from training what makes BFS the right approach, not from spotting "BFS" in the problem name.

The solution builds from BFS's invariant. At any moment, the queue contains every node whose shortest distance from the source is exactly the distance you're currently processing. You aren't recalling "this one used a deque." You're reasoning: enqueue the start at distance zero, expand neighbours level by level, return as soon as you pop the target.

from collections import deque

def shortest_path(graph, start, target):
    queue = deque([(start, 0)])
    visited = {start}
    while queue:
        node, dist = queue.popleft()
        if node == target:
            return dist
        for nbr in graph[node]:
            if nbr in visited:
                continue
            visited.add(nbr)
            queue.append((nbr, dist + 1))
    return -1

Before you run anything, you trace it on a four node example. Walk the queue. Check visited. Verify the returned distance matches what you'd expect for a path you can see in your head. The mental dry run catches bugs the random test and submit loop misses, and it's the exact behaviour interviewers watch for: verifying correctness without leaning on the compiler.

You submit. It passes. Eight minutes still on the timer. Not because you rushed, but because identification took two minutes instead of fifteen, and the construction followed the invariant rather than trial and error.

Recognition under pressure matters more than recall in comfort.

That is what FAANG ready looks like. Not "I feel confident." A repeatable, observable performance.

A second pass on a different family

Now you change family. Pick a variable sliding window problem you haven't seen. The constraint shape: a contiguous range over an array or string, a flexible boundary that grows and shrinks, an objective that asks for the longest, shortest, or maximum window meeting some condition.

The recognition again happens within the first three minutes, before any code. The constraints match the variable sliding window's three triggers, you can name the invariant the window has to maintain, and you write the same expand then contract skeleton you'd write for any problem in the family.

def variable_window(arr, valid):
    left = 0
    best = 0
    state = init_state()
    for right in range(len(arr)):
        state = include(state, arr[right])
        while not valid(state):
            state = exclude(state, arr[left])
            left += 1
        best = max(best, right - left + 1)
    return best

You fill in init_state, include, exclude, and valid for the specific problem. The skeleton stays the same. That's the marker of a pattern that's actually generalised in your head: you write the skeleton first, then specialise.

When a pattern generalises, you stop memorising solutions and start specialising frameworks.

If you pass this one too, you've got two of three. One more, on a third family you haven't over practised, decides it.

When you fail the test

Most engineers don't pass all three on the first attempt. That's expected. A clean three for three on the first try usually means the families were too comfortable.

One family failed. You know the pattern at a surface level but haven't internalised the identification triggers or the construction skeleton. Go back to the foundational material for that family. Don't just grind more problems in it. Study what makes the pattern applicable, the constraint combinations that point to it, the invariant every problem in the family shares. Once you can articulate that without notes, retest with a different unseen problem.
Two families failed. You likely have one strong area where you've over practised and shallow gaps everywhere else. Common for engineers who spent months on arrays or trees because the work felt productive. Broaden the coverage. Spend focused time on the families where the understanding is thin.
All three failed. The preparation has been building near transfer without building far transfer. That's a method gap, not a talent gap. Shift from solving high volumes to studying fewer problems more deeply. Focus on identification and constraint analysis rather than just reaching a correct solution.

One catch. Don't retake the test with the same problems. A retest on a problem you've already seen, even if you failed it, measures recall instead of reasoning. Find a different unseen problem in the same family.

The four signals most engineers use instead

Before the test, it helps to name the signals you've probably been using, and why each one lies.

Problem count. Tells you nothing about how the problems were solved. Someone at 120 problems with genuine pattern depth outperforms someone at 400 who relied on hints for half of them.
Topic completion. You finished sliding window two months ago and haven't touched it since. Completion isn't retention. Spacing matters. The performance you had on week three doesn't survive without revisits.
Speed on familiar problems. Two Sum in two minutes feels like fluency. It's actually retrieval of a stored solution. The moment a novel problem looks similar but has different constraints, the speed evaporates.
Peer comparison. Your friend got into Google in six months. That ignores their background, their pattern coverage, how they practised, and what level they interviewed for.

The three family test bypasses all four. It doesn't care about the count, the completion checkmarks, the recall speed, or anyone else's timeline. It measures one thing: can you construct a solution to a novel problem, under pressure, across families.

Setting up the conditions yourself

The hardest part of the test is replicating real interview conditions. Solving at your desk, documentation a tab away, with the timer optional, doesn't replicate a forty five minute FAANG round.

What you actually need: a source of unseen mediums in the families you've studied (the variable sliding window lesson covers one family if you haven't been through it before), a way to hide the problem name (a friend covering it, or a browser extension that aliases the title), a kitchen timer set to twenty minutes, and the discipline to stop after two failed runs. The conditions matter. The test fails the moment you peek at hints or let the timer slide.

I keep noticing the same two things across engineers who run this test for the first time. The ones who fail one family and immediately know why aren't far from ready, they're a couple of weeks of focused study away. The ones who fail all three and panic into more volume usually need to step away from the problem bank for a week and re read the foundational material on identification and invariants. The diagnostic is more useful than the score.

If you're stuck in the “I've solved a lot but still don't know if I'm ready” phase, the problem usually isn't effort.

It's measurement.

I wrote a longer breakdown covering:

per family readiness signals
common failure patterns
and what to fix when one family collapses under pressure

Full breakdown here

What's the specific moment you knew you weren't ready yet? A particular problem, a frozen minute in a mock, or the cumulative shape of practice that just felt off?