Binary Search Trees

1The mental model (what this really is)#

A binary search tree is a binary tree with one promise attached to every single node.

Everything in my left subtree is smaller than me. Everything in my right subtree is larger than me.

• Not just my immediate children. My entire left subtree and my entire right subtree.
• That word "entire" is where most bugs live. Section 4 shows exactly how ignoring it produces a validator that approves trees it should reject.

The insight that changes everything: a BST is a sorted array that someone folded up.

• Walk the tree left, then node, then right and the values come out in sorted order. Every time.
• That walk is called in-order traversal.
• It is the secret weapon behind a surprising number of problems: k-th smallest, validation, finding the two swapped nodes in Recover BST. All of them.

So when you see a BST, hold two thoughts at once.

• Search structure: I can throw away half the tree at each step, so my search costs O(height), not O(n).
• Sorted list: if I walk it in-order, it is already sorted.

2How to recognize it (the signals in a problem)#

You are looking at a BST problem when any of these fire.

• The problem literally says "binary search tree." Easy tell, but read the constraint: the trick is usually "use the ordering, do not treat it as a plain binary tree." If an O(n) scan would solve it, the BST label is a hint that O(height) is the expected answer.
• You need the k-th smallest or k-th largest. That is in-order traversal with a counter, stopping at the k-th visit.
• You need to validate a tree is a valid BST. Classic trap, covered in section 4.
• You need find, insert, or delete on a sorted structure. Target O(height), which is O(log n) on a balanced tree.
• The words "closest value," "range sum," "elements between low and high," or "successor / predecessor" appear. All exploit ordering so you can prune whole subtrees instead of visiting them.

The tell that separates strong from average:

• The average candidate solves a BST problem the way they solve a plain binary tree, by visiting every node.
• The strong candidate asks "can I skip a whole subtree here?"
• If the answer was yes and you still visited everything, you turned an O(log n) problem into O(n) and the interviewer noticed.

3The template (how it works, with pseudocode)#

Almost every BST operation is the same shape: stand at a node, compare, go left or right. Here is the core search.

function search(node, target):
    while node is not null:
        if target == node.val:
            return node
        else if target < node.val:
            node = node.left     # target must be on the left
        else:
            node = node.right    # target must be on the right
    return null

• That is the whole engine.
• It is iterative, so O(1) extra space, no recursion stack.

Insert is the same walk. When you fall off the tree (hit null), that empty spot is where the new value belongs.

function insert(node, val):
    if node is null:
        return new Node(val)
    if val < node.val:
        node.left = insert(node.left, val)
    else:
        node.right = insert(node.right, val)
    return node

And the one to memorize cold, in-order traversal, because it gives you sorted output.

function inorder(node, visit):
    if node is null: return
    inorder(node.left, visit)
    visit(node.val)              # values arrive in sorted order
    inorder(node.right, visit)

Three moves, and you can derive the rest at the whiteboard:

• Compare and branch.
• Recurse down the one side you chose.
• Walk in-order for a sorted view.

4A worked example (walk through one problem step by step)#

Let me take a problem that looks annoying and show how the BST view makes it short: validate whether a binary tree is a valid BST. This is the single most asked BST question I see, so get it cold.

The naive attempt (I see it constantly):

• Check that each node's left child is smaller and right child is larger.
• Recurse. Done.
• It is wrong. Here is why.

        10
       /  \
      5    15
          /  \
         6    20

Figure. Look at node 6. Its parent 15 is larger, so the local "my children are in order" check passes. But 6 sits in the right subtree of 10, so it must exceed 10, and it does not. The tree is invalid and the naive check approves it. This is the exact case the interviewer is watching for.

The real rule is the invariant from section 1.

• Everything in the right subtree of 10 must exceed 10.
• So each node is not just bounded by its parent. It is bounded by a range that tightens as you descend.

function isValid(node, low, high):
    if node is null:
        return true
    if node.val <= low or node.val >= high:
        return false
    return isValid(node.left, low, node.val)
       and isValid(node.right, node.val, high)

isValid(root, -infinity, +infinity)

Trace it on the bad tree:

• Root 10, range (-inf, +inf). Fine. Go right with range (10, +inf).
• Node 15, range (10, +inf). Fine. Go left with range (10, 15).

• Node 6, range (10, 15). Is 6 greater than 10? No, 6 is below the low bound. Return false.

• The bug the naive version missed is caught instantly, because we carried 10 down as a hard floor.

• Runs in O(n) time (each node checked once) and O(h) stack space.

A second, even cleaner way to explain it:

• Do an in-order traversal and check the output is strictly increasing.
• Keep one "previous value" variable. The moment the current value is not strictly greater, return false.
• If the sorted walk ever goes flat or backward, it is not a valid BST.

5Variations and gotchas (what the interviewer throws next)#

A few patterns show up again and again once you know the base.

K-th smallest element.

• In-order traversal, stop at the k-th visit. You do not finish the walk.
• Iterative in-order with an explicit stack lets you stop early and stay O(h) extra space.
• Time is O(h + k): you descend once, then pop k times.

Lowest common ancestor in a BST.

• This is a BST-only shortcut. Do not drag in the general-tree LCA (O(n), full recursion).
• Walk down from the root: both targets smaller than the current node, go left. Both larger, go right.
• The moment they split (one smaller, one larger, or one equals the node), you are standing on the LCA.
• O(height), iterative, no recursion stack. Solve it the general-tree way and the interviewer asks "but it is a BST, can you do better?", so start with the better answer.

Insert and delete.

• Insert is the same walk as search until you hit null. Easy.
• Delete is the one that trips people:
• Leaf: null it out.
• One child: splice the child up into its place.
• Two children (the hard case): replace the node's value with its in-order successor (smallest value in its right subtree: go right once, then left until you cannot), then delete that successor from its old spot.
• Practice the two-child case by hand. The "then delete the successor" half is where people forget a step, and it is a favorite follow-up.

Duplicates.

• Interviewers love to ask. Decide a convention (go right on equal, say) and state it out loud before you write code.
• Your validation bounds must then use strict vs non-strict comparison consistently, or you get subtle wrong answers that pass small tests and fail the one with a repeated value.

The balance problem.

• A BST only gives O(log n) if it is balanced.
• Insert 1, 2, 3, 4, 5 in order and you get a straight line, a linked list wearing a tree costume, and every operation becomes O(n).
• If the interviewer stresses worst case, name self-balancing trees (AVL, red-black) or at least that the structure can degrade. You rarely implement balancing in an interview, but naming it earns credit and costs one sentence.

If your BST search is O(n), you are not using the BST. That is the whole point of the question.

6Complexity#

For a BST with n nodes and height h (roughly log n when balanced):

Reading the table:

• Space: recursion uses O(h) stack. Balanced tree, O(log n). Degenerate, O(n).
• The full traversal always touches all n nodes, so you cannot beat O(n) there. Targeted searches should be O(h).
• If your "search" is O(n), you are not using the BST property.

The honest trade-off (say this out loud):

• A BST gives ordered operations a hash set cannot: range queries, successor, predecessor, k-th smallest, "all values in [low, high]".
• A hash set gives O(1) average lookup but zero order, so it cannot answer "what is the next-largest key" without scanning everything.
• Reach for a BST when order matters, a hash set when it does not. Saying that tells the interviewer you picked the structure on purpose.

7Mistakes that cost people the round#

Checking only immediate children for validity.

• The number one BST mistake, the one from section 4.
• Carry a min/max range down the tree instead. We walked through exactly why the local check passes the invalid tree with node 6.

Using the wrong infinity.

• Validating with integer bounds, a node holding the maximum possible integer breaks naive comparisons (you cannot set the bound one higher).
• Use open bounds and pass the node's value itself as the new bound, or use a nullable "previous value" with in-order so there is no sentinel at all. State your assumption about the value range.

Treating a BST like a generic binary tree.

• Visit every node to find one value and you threw away the ordering.
• The interviewer handed you a sorted structure on purpose. Ignoring it reads as "did not notice the input."

Forgetting the degenerate case.

• Say "this assumes the tree is reasonably balanced, worst case it degrades to O(n)." Five seconds, and it signals maturity about real inputs.

Botching two-child deletion.

• Get the in-order successor logic right, and actually remove the successor from its old spot after copying its value up.
• Dry-run it on paper before you claim it works. This is the follow-up that separates "memorized it" from "understands it."

Recursion with no base case for null.

• Half of tree bugs are a missing if node is null.
• Write that line first, always, before anything else in the function.

8Your practice path (problems you can now solve)#

Do these in order. Names only, go solve them yourself. That is where the learning happens.

Warm up (Easy):

• Search in a Binary Search Tree
• Minimum Absolute Difference in BST
• Range Sum of BST
• Convert Sorted Array to Binary Search Tree

Core (Medium), this is where interviews live:

• Validate Binary Search Tree
• Kth Smallest Element in a BST
• Lowest Common Ancestor of a Binary Search Tree
• Insert into a Binary Search Tree
• Delete Node in a BST
• Binary Search Tree Iterator
• Convert BST to Greater Tree

Stretch (Hard):

• Recover Binary Search Tree
• Count of Smaller Numbers After Self (BST as a counting structure)
• Serialize and Deserialize BST

How to know you are ready:

• Do the Core list cold, narrating the two views (search structure and sorted-when-walked) as you go.
• Do not skip Delete Node and BST Iterator because they feel fiddly. Those are the two that most often show up as the "now make it harder" follow-up.

9Where this shows up#

BST questions are bread and butter at companies that lean algorithmic.

• Google, Meta, Amazon, and Microsoft all pull from the Core list, especially Validate BST, Kth Smallest, and LCA.
• Expect them in the phone screen and the first onsite round, often as the warm-up before a harder graph or dynamic-programming question.
• Startups borrowing FAANG-style loops use them the same way: the opener that confirms you can write clean recursion under light pressure before they turn up the heat.
• BST Iterator in particular is a favorite because it tests whether you really understand in-order traversal or just memorized it. You cannot fake the "pause between values" part with a copied snippet.

Want to see exactly which of these pop up where? Check the company guides to map this pattern to the rounds you are actually interviewing for.