DSA · Binary search trees

Binary search, built out of pointers

Q: What does an inorder traversal of a BST give you, and what does it cost?

The values in increasing order, in O(n) time and O(h) extra space for the recursion stack. It falls straight out of the definition: inorder does left subtree, then the node, then right subtree, and the left subtree is exactly the set of values smaller than the node. Our tree prints 1 3 4 5 7 8 9 .

Q: How do you find the kth smallest value in a BST?

Run an inorder walk with a counter and stop the moment the counter reaches k. That is O(h + k) time and O(h) space, and it never touches the rest of the tree. Collecting the whole inorder into a list first works but costs O(n) time and O(n) space and gets marked down. If these queries are frequent, store a subtree-size field in each node and you can answer in O(h) by comparing k with the size of the left subtree.

Q: How do you find the floor of x — the largest value that is at most x?

Descend as usual, but remember candidates as you go. If the node equals x, that is the answer. If the node is smaller than x it is a possible floor, so record it and go right hoping for something closer. If the node is bigger than x, record nothing and go left. When you fall off the bottom, the last recorded value is the floor. Ceil is the mirror image: record when the node is bigger than x, then go left.

A BST spends one comparison per level, so a lookup costs the height of the tree and not the size of the data. You will insert seven values by hand, search one, and get all three delete cases right — including the two-children case that needs the inorder successor.

Descend a live tree, then delete a node →

Case 1 · leafcut the one link from its parent

→

Case 2 · one childthe child is lifted into its place

→

Case 3 · two childrenthe inorder successor takes over

01 The idea

One comparison, one level down

A sorted array lets you binary-search, but inserting into the middle of it costs up to n shifts, because every later element has to move over. A binary search tree keeps the halving power and makes insertion cheap. It stores the order in links instead of in positions.

Each node holds a value and two links, called left and right. Stand on any node and one comparison settles everything: if your value is smaller it can only be in the left subtree, if it is bigger it can only be in the right one. You follow one link, and the entire other subtree drops out of the search. On a seven-node tree that takes the candidate count from 7 to 3 to 1 — the same three reads binary search needs on seven sorted values, done with pointers instead of indices.

Every value in a node's left subtree is smaller than the node, and every value in its right subtree is bigger. Hold that promise at every node and one comparison per level is enough to find anything.

BST propertyThe promise above, checked at every node against its whole subtree — not just against its two children. That difference is what makes "validate a BST" a real question and not a one-liner.

HeightThe number of links on the longest path from the root down to a leaf. Our tree has height 2. Every operation here costs O(height), which is O(log n) only when the tree is balanced.

Inorder successorThe next value up from a node: go right once, then left as far as you can. It is the smallest value in the right subtree, and it is the value that takes over when you delete a node with two children.

02 Hand trace

Insert 5 3 8 1 4 7 9, then search for 4

Start with an empty tree and insert 5 3 8 1 4 7 9 in exactly that order. Every insert is a search that failed: you compare your way down, and the empty link you fall off is where the new node hangs. Each row below is one insert — the boxes are the nodes you compared against, and the green box is where the value landed.

insert 55tree was empty · 5 becomes the root

insert 3533 < 5 · left of 5

insert 8588 > 5 · right of 5

insert 15311 < 5 left · 1 < 3 left

insert 45344 < 5 left · 4 > 3 right

insert 75877 > 5 right · 7 < 8 left

insert 95899 > 5 right · 9 > 8 right

Seven inserts, and this is the tree they build. Height 2, four leaves, and every level filled — the best shape seven nodes can take.

        5          <- root, level 0      /   \     3     8       level 1    / \   / \   1   4 7   9     level 2, all leaves

Now search for 4. Read the tree's values out in inorder — left subtree, node, right subtree — and you get 1 3 4 5 7 8 9, sorted, which is what inorder always does to a BST. The trace below lays those seven values in a row so you can watch the descent the way you watched a binary-search window. The rose box is the node you are standing on.

inorder1345789sorted · 7 candidates

at root 513457894 < 5 · go left · drop 5 7 8 9

at 313457894 > 3 · go right · drop 1 and 3

at 413457894 = 4 · found

result13457893 comparisons · level 2 · 7 → 3 → 1

Three comparisons, and the candidate count went 7 → 3 → 1. That is not a coincidence. A balanced BST standing over a sorted sequence hands you the same middle elements binary search would pick, so it costs the same number of reads. What you pay for it is a pointer per link — and what you buy is that inserting 6 does not shift anything.

03 The code

One descent, and the three ways a delete ends

Search and insert are the same walk, so they share the code on the left. Delete is that walk plus one decision, and the decision is the part interviews probe: how many children does the doomed node have? There are three answers and each one restructures the tree differently.

Search — and insert, for free

node = rootwhile node is not null:    if x == node.val:  return FOUND    if x <  node.val:  node = node.left    else:              node = node.rightnot found -> hang a new node holding x here

Delete — the three cases

find x, remembering its parentif x has no children:                # case 1    cut the link from the parentelse if x has one child:             # case 2    point the parent at that childelse:                                # case 3    s = leftmost node of x.right      # successor    x.val = s.val                     # copy it up    delete s  (it has no left child)

Why insert needs no logic of its own. Insert is a search that failed. You compare your way down exactly as search does, and the empty link you fall off is the only place the new value can sit without breaking the promise in section 01 — that is why the insert trace above is just seven searches. It also explains the cost: O(height) for a BST, against O(n) for a sorted array, where inserting 6 shifts 7, 8 and 9 over by one.

Why the inorder successor, and not any other node. Whatever value takes the deleted node's place has to be bigger than everything in its left subtree and smaller than everything in its right subtree. Exactly two values in the whole tree qualify: the largest in the left subtree (the inorder predecessor) and the smallest in the right (the successor). Anything else breaks the property somewhere below. Either one is correct — pick a side and stay consistent.

Why case 3 never turns into another case 3. The successor is the leftmost node of the right subtree, so by construction it has no left child. A node with no left child is a leaf or a one-child node, so the second delete is always case 1 or case 2. One delete is therefore one descent to the node plus one descent to the successor: still O(height).

The three cases, side by side

Case	What you do	On our tree
1 · no children	Cut the link from its parent. Nothing else in the tree moves.	Delete 1: the left link of 3 becomes empty. Inorder is now 3 4 5 7 8 9 — still sorted.
2 · exactly one child	Point the parent straight at that child. The whole subtree under it slides up one level.	With 1 already gone, 3 has only the child 4. Delete 3: the left link of 5 now points at 4.
3 · two children	Take the inorder successor — right once, then left as far as it goes. Copy its value into the node, then delete the successor.	Delete 5 from the full tree: go right to 8, left to 7, so 7 moves up and 8 loses its left child.

Before · delete 5

        5      <- two children      /   \     3     8    / \   / \   1   4 7   9   7 = successor

After · 7 moved up

        7      <- successor is now the root      /   \     3     8    / \     \   1   4     9   8 lost its left child

Check a delete by reading the inorder walk. Before: 1 3 4 5 7 8 9. After: 1 3 4 7 8 9. Still sorted, and only the deleted value is missing. If your inorder comes out unsorted, the restructuring broke the property — and that check takes ten seconds on paper.

05 Cheat sheet

Numbers worth memorising

Case	Cost	What causes it
Search, insert, delete — balanced tree	`O(log n)`	One comparison per level, and a balanced tree has about log₂ n levels. Our 7-node tree has 3 levels, so at most 3 comparisons.
Search, insert, delete — skewed tree	`O(n)`	Insert 1 2 3 4 5 6 7 in that order and every node gets only a right child. The tree is a linked list with a wasted pointer per node.
Find the minimum or maximum	`O(h)`	Leftmost node for the minimum, rightmost for the maximum. Walk one direction until that link is null — no comparisons needed. Still one step per level, so `O(log n)` balanced and `O(n)` on a chain.
Inorder traversal (sorted output)	`O(n)`	Every node is printed once. This is optimal — you cannot emit n sorted values for less.
kth smallest, controlled inorder	`O(h + k)`	Inorder with a counter that stops at the kth value. Only the first k nodes are ever touched.
Space — recursion stack	`O(h)`	One frame per level for any recursive walk: `O(log n)` balanced, `O(n)` on a skewed tree. The iterative descent in section 03 keeps no stack at all — `O(1)`.
Space — the tree itself	`O(n)`	n nodes, each carrying a value and two links.

Inorder is sortedAn inorder walk of any BST prints the values in increasing order. That single fact is behind validate-a-BST, kth smallest, and recovering two swapped nodes — and it is the fastest way to check your own answer on paper.

A plain BST never balances itselfNothing in insert looks at the height. Sorted or nearly sorted input builds a chain and every operation degrades to O(n). AVL and red-black trees add rotations to stop that; this one does not.

Duplicates need a policyThe property as stated leaves no room for equal values. Pick one: reject them, keep a count field in the node, or always send them right and compare with ≤. Say which you chose before you write code.

06 Where & why

When the order matters as much as the lookup

A BST is not the fastest way to answer "is x present". A hash table does that in O(1) and does not care about order at all. What the tree gives you is everything the hash table cannot: the value just below x, the value just above it, the kth smallest, a range, and the whole set in sorted order for the price of one walk.

Reach for it when…

The questions are about orderFloor, ceil, successor, predecessor, everything between a and b, the kth smallest. A hash table answers none of these without sorting its entire contents first.

The data keeps changingInsert and delete are O(height). A sorted array gives you the same lookups, but a single insert shifts up to n elements.

You also need sorted outputOne inorder walk emits every value in order in O(n), with no separate sort step and no extra array.

You need both ends and the middleMinimum is the leftmost node, maximum is the rightmost, and unlike a heap you can still reach everything in between in O(height).

Use something else when…

Situation	Better choice	Why
You only ever ask "is x present", by exact key	Hash table / dictionary	O(1) average beats O(log n), and there is no ordering to maintain.
The data is fixed and you only read it	Sorted array + binary search	Same O(log n) lookups with no pointers, less memory and far better cache behaviour.
Keys can arrive sorted, or an attacker picks the order	Red-black or AVL tree (std::map, TreeMap, SortedDict)	They rotate on insert to hold the height at O(log n). A plain BST silently becomes a chain and every operation turns O(n).
You only ever need the smallest item, repeatedly	Binary heap	O(1) peek, a much smaller constant, and it never pays to keep the rest ordered.

In production you will use std::map, TreeMap or SortedDict, and all three are balanced trees underneath — nobody ships a hand-written plain BST. Interviews still ask for it, because the two-children delete and the range-bounds validation are exactly where people fall over, and because every balanced tree is this tree plus rotations.

07 Interview questions

What interviewers actually ask

Eleven questions in the order an interview escalates: what it is, how fast, why that fast, then the delete and validate follow-ups that decide the round.

What is a binary search tree?

A binary tree where, for every node, all values in its left subtree are smaller and all values in its right subtree are larger — and that has to hold for the whole subtree, not just the two children. The payoff is that one comparison at a node rules out an entire subtree, so search, insert and delete each cost one step per level. On the tree built from 5 3 8 1 4 7 9 any of the 7 values is reachable in at most 3 comparisons.

Why do you say search is O(h) and not O(log n)?

Because the real cost is the number of levels you walk, and the height h equals log₂ n only when the tree is balanced. A plain BST never rebalances, so a bad insert order gives a tall thin tree and the same code becomes O(n). Saying O(log n) without the word "balanced" is the answer interviewers push back on.

Which insert order gives the worst possible tree, and what does it cost?

Already sorted input, or reverse sorted. Every new value goes to the same side, so you end up with a chain of height n − 1 — a linked list with one wasted pointer per node — and search, insert and delete all become O(n). Nearly sorted real data does the same thing, which is why libraries ship red-black trees instead.

Walk me through deleting a node that has two children.

Find the inorder successor: go right once, then left as far as you can, so it is the smallest value in the right subtree. Copy that value into the node you are deleting, then delete the successor from the right subtree. The successor is a leftmost node, so it has no left child, which makes that second delete the leaf case or the one-child case. Deleting 5 from our tree brings 7 up to the root and leaves 8 without a left child.

Why the inorder successor specifically? Could you use some other node?

Because only two values in the whole tree can legally sit where the deleted node sat, and the successor is one of them. Whatever takes that place has to be bigger than everything in the left subtree and smaller than everything in the right one, and exactly two values satisfy that: the largest in the left subtree, which is the inorder predecessor, and the smallest in the right, which is the successor. Either is correct and anything else breaks the property. Always taking the same side is what makes a BST lean over many deletes, so some implementations alternate.

In the two-children case, can deleting the successor turn into another two-children case?

No — it costs at most one extra step. The successor is the leftmost node of the right subtree, so by construction it has no left child, and a node with no left child is either a leaf or a one-child node. So case 3 reduces to case 1 or case 2 exactly once and never recurses again. The whole delete stays O(h).

How do you check whether a binary tree is a valid BST?

Carry an allowed range down the recursion: every node must satisfy low < val < high, the left child inherits (low, val) and the right child inherits (val, high). Comparing each node only against its two children is the classic wrong answer — a value can be smaller than its parent and still too big for a grandparent, and that broken tree passes the child-only check. The other correct answer is that an inorder walk must be strictly increasing.

What does an inorder traversal of a BST give you, and what does it cost?

The values in increasing order, in O(n) time and O(h) extra space for the recursion stack. It falls straight out of the definition: inorder does left subtree, then the node, then right subtree, and the left subtree is exactly the set of values smaller than the node. Our tree prints 1 3 4 5 7 8 9.

How do you find the kth smallest value in a BST?

Run an inorder walk with a counter and stop the moment the counter reaches k. That is O(h + k) time and O(h) space, and it never touches the rest of the tree. Collecting the whole inorder into a list first works but costs O(n) time and O(n) space and gets marked down. If these queries are frequent, store a subtree-size field in each node and you can answer in O(h) by comparing k with the size of the left subtree.

How do you find the floor of x — the largest value that is at most x?

Hard

Exactly two nodes of a valid BST had their values swapped by mistake. Restore the tree in O(n) time and O(h) extra space.

Follow-up

The inorder walk is sorted except for the damage, and the damage has two shapes: if the two culprits are neighbours in the inorder order you see one dip, otherwise you see two. Handling only the two-dip shape passes most tests and fails the adjacent case.

Show the hint

Walk inorder while remembering the value you saw immediately before. Every place where the previous value is bigger than the current one is evidence — collect all of them before you decide which two nodes to swap back.