cf.completefrontend
TREES & TRIES · CORE

Binary search tree operations

Keep values in a tree where everything on the left is smaller and everything on the right is bigger, so each search or insert follows one path down.

Time O(h)Space O(1)15 practice problemsStep-through picture

The idea

A binary search tree, or BST, is a binary tree with one rule at every node: all values in its left subtree are smaller than the node's value, and all values in its right subtree are bigger (or, if you allow duplicates, bigger or equal).

That rule turns a search into a walk down one path. Compare the value you want with the current node. If it is smaller, it can only be on the left; if bigger, only on the right. Each step skips a whole subtree, like binary search skips half a list.

Inserting uses the same walk: go left or right until the child you need is missing, then put the new node there. Reading a BST inorder (left, node, right) lists every value in sorted order.

An everyday example

Finding a word in a paper dictionary

You open a dictionary in the middle. The word you want is "maple" and the page shows "lantern", so you only look in the second part. You open that part in the middle and see "pepper", so now you look before it. Each look rules out a big part of the book. To add a new word, you follow the same looks until you find the exact gap between two words where it belongs.

How the example maps to the code
In the exampleIn the code
The page you are looking atnode
"The word comes before this page"val < node.val, so go to node.left
"The word comes after this page"otherwise go to node.right
Finding the empty gap where a new word fitsnode.left === null or node.right === null
Writing the word in the gapnode.left = fresh or node.right = fresh

From the slow way to binary search tree operations

  1. Say you keep a set of values that grows over time, and you often ask "is x here?". An unsorted array answers in O(n) per question. A sorted array answers in O(log n) with binary search, but every insert has to shift up to n items to keep the order. You want fast search and fast insert together.
  2. Binary search works because one comparison with the middle item tells you which half to keep. Picture freezing those choices: the first middle item becomes a node, the middle of the left half becomes its left child, and the middle of the right half its right child. You get a binary tree where everything on a node's left is smaller than it and everything on its right is at least as big.
  3. In this shape, a search is a walk down one path: compare, then go left or right. And inserting needs no shifting, because nodes are linked by pointers instead of sitting side by side in memory. You follow the same path a search would take until the child you need is missing, and you hang the new node there.
  4. The cost is the length of that path, which is at most the tree's height. Values that arrive in random order give a height close to log n, while sorted values give a chain. Following one path and attaching at the first empty spot is BST insert, and search and delete are the same walk with a different ending.

How it works

  1. Make the new node fresh. If the tree is empty, fresh is the whole tree.
  2. Start at the root with node = root.
  3. If val < node.val, the new value belongs on the left. If node.left is empty, attach fresh there and stop; otherwise move to node.left.
  4. Otherwise it belongs on the right. If node.right is empty, attach fresh there and stop; otherwise move to node.right.
  5. Return root. Searching is the same walk, returning the node when node.val === val and null when you fall off the tree.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function bstInsert(root, val) {
  2. const fresh = new TreeNode(val);
  3. if (root === null) return fresh;
  4. let node = root;
  5. while (true) {
  6. if (val < node.val) {
  7. if (node.left === null) {
  8. node.left = fresh;
  9. break;
  10. }
  11. node = node.left;
  12. } else {
  13. if (node.right === null) {
  14. node.right = fresh;
  15. break;
  16. }
  17. node = node.right;
  18. }
  19. }
  20. return root;
  21. }

How fast it is

TimeO(h)
Extra memoryO(1)

Each step moves one level down, so the walk is at most the height h. The loop keeps only node, so the extra memory is constant.

  • Best caseO(1)

    The tree is empty, or the root's child on the needed side is missing, so the new node attaches after at most one comparison.

  • Average caseO(log n)

    Values inserted in random order. In a test with a million shuffled values, nodes were about 26 levels deep on average and the deepest was 50, only a small multiple of log₂ n, which is about 20.

  • Worst caseO(n)

    Values inserted in sorted order, like 1, 2, 3, ..., n. Each one goes right at every node, the tree becomes a chain, and the n-th insert walks past n - 1 nodes.

Common mistakes

  • Checking only a node and its direct children to validate a BST. A value deep in the left subtree can still be bigger than an ancestor. Pass down the allowed min and max range instead.
  • Inserting sorted data and expecting fast searches. The tree becomes a chain. Shuffle the input or use a self-balancing tree.
  • When removing a node with two children, replacing it with any child. Use the inorder successor (or predecessor) so the order rule still holds.
  • Not deciding where equal values go. Pick one side (here, the right) and use it the same way in search, insert, and remove.

When to use it

Look for these clues in a problem:

  • The input tree is described as sorted: "every value on the left is smaller".
  • You need to search, insert, or remove values while keeping them in order.
  • The question asks for the k-th smallest value, the closest value, or all values in a range.
  • An inorder walk would give a sorted list, and the problem is easy on a sorted list.

Check yourself

Answer each one in your head first, then open it.

Why does insert never need to move existing nodes?

It only fills an empty child slot with a new leaf. Every existing node keeps its parent and its children, so no subtree changes.

In the trace, why does the second 15 end up as the left child of 16?

At the first 15, the tie sends it right, to 16. There 15 < 16 sends it left, and that slot is empty.

What is the height after inserting 5, 4, 3, 2, 1 into an empty tree?

5. Each value is smaller than every value before it, so it goes left at every node and the tree is a chain leaning left.

Why is the inorder walk of a BST sorted?

Inorder lists the left subtree, then the node, then the right subtree. The rule says every left value is smaller and every right value is at least as big, and the same holds inside each subtree.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 15 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The property every operation must keep: for every node, all values in its left subtree are less than node.val, and all values in its right subtree are greater than or equal to it. This is a rule about whole subtrees, not just direct children, and it's the reason an inorder walk comes out sorted.

Insert keeps it because of the path it takes. Each time the walk goes left at a node, the new value is less than that node; each time it goes right, the new value is at least as big. So the new value ends up on the correct side of every ancestor on its path, and nodes off the path are not touched. It attaches as a new leaf, so no existing subtree changes.

The loop ends because each step moves one level down and the tree's height is finite, so some child on the path must be null. Search uses the same reasoning: if the value is in the tree, the rule says it can only be on the side the walk chooses, so skipping the other side never loses it.

Going deeper

3 more ideas

Why one path is enough

At a node with value v, every value on the left is less than v and every value on the right is at least v. If the value we want is less than v, it cannot be anywhere on the right, so the right subtree is skipped entirely. Each step goes one level down, so the work is at most the tree's height.

Removing a node

A leaf is simply cut off. A node with one child is replaced by that child. A node with two children is the tricky case: find its inorder successor, the smallest value in its right subtree (go right once, then left as far as possible). Copy that value into the node, then remove the successor from the right subtree; the successor has no left child, so that removal is one of the easy cases.

Height decides the speed

Search and insert cost O(h) for height h. If values arrive in random order, h is about log n. If they arrive already sorted, like 1, 2, 3, 4, every node goes right and the tree becomes a chain with h = n, so each operation is O(n). Self-balancing trees such as AVL trees fix this by rotating nodes after inserts.

Work it by hand

Every step in a table, with why

Insert 16, then a second 15, into a 7-node search tree. The second insert meets an equal value, so the trace shows where ties go.

root = [11, 6, 19, 3, 8, 15, 24]; bstInsert(root, 16), then bstInsert(root, 15)

Stepvalnode.valTestWhat happensWhy
1161116 < 11 is falsego right to 1916 is not less than 11, so it belongs in the right subtree. The whole left side, 6, 3, and 8, is skipped.
2161916 < 19go left to 1516 is smaller than 19, and 19 has a left child, so the walk moves down to it.
3161516 < 15 is false15.right is null: attachThe right child of 15 is empty, so the new node goes there and the loop stops with break. The root is returned unchanged.
4151115 < 11 is falsego right to 19Now insert a second 15, a duplicate of a value already in the tree.
5151915 < 19go left to 15Same path as before so far.
6151515 < 15 is falsego right to 16A tie. The code goes left only on strictly smaller values, so an equal value goes right. This is the rule this code picked for duplicates.
7151615 < 1616.left is null: attachThe new 15 becomes the left child of 16. It is in the right subtree of the first 15, as the tie rule says, and still left of 16, as the order rule says.

The tree is now [11, 6, 19, 3, 8, 15, 24, null, null, null, null, null, 16, null, null, 15], and its inorder is [3, 6, 8, 11, 15, 15, 16, 19, 24], still sorted. The first insert made 3 comparisons and the second made 4, one per level walked.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Binary search tree operationsO(h)O(1)Data changes often, you need sorted order or nearest values, and inserts come in a fairly random order.
Sorted array with binary searchO(n)O(1)Search is O(log n), but each insert shifts up to n items. Pick it when the data rarely changes after it's built.
Hash setO(1)O(n)You only ask "is it there?" and never need order, ranges, or the nearest value.
AVL treeO(log n)O(log n)Inputs may arrive sorted or in an unlucky order, and you need O(log n) per operation guaranteed.

Extra memory: O(1) extra: the loop keeps only node and fresh. A recursive insert would use O(h) stack instead. The tree itself takes O(n).

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Binary search tree operations and the other approaches, on a scale where each line up is 10 times more steps.
  • Binary search tree operations, Sorted array with binary search O(h)
  • Hash set O(1)
  • AVL tree O(log n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Binary search tree operations101,0001 million
Sorted array with binary search101,0001 million
Hash set111
AVL tree31020

Inputs that need care

5 tricky inputs
An empty tree: root = null
Line 3 returns fresh as the new root. The caller must store it, as in root = bstInsert(root, 7), or the new node is lost.
A duplicate, like the second 15 in the trace
It goes right at the equal node and settles in that node's right subtree. Search must follow the same rule: on val === node.val it has found a match, and any further copies are on the right.
Sorted input: 1, 2, 3, 4, 5
Each insert goes right every time and the tree is a chain of height 5. Searches become linear. Shuffle the input first or use a self-balancing tree.
Numbers stored as strings, like "10" and "9"
< compares strings character by character, so "10" < "9" is true and the order is wrong. Convert every value to the same type, or pass a compare function.
NaN as a value
NaN < x is always false, so NaN always goes right, and a search for it with === never matches. Reject it before inserting.

Variations and follow-ups

Twists interviewers add

Search

The same walk, but return the node as soon as node.val === val. If the walk falls off the tree (node === null), the value isn't there. It's this loop with the attach step replaced by return null.

Delete

Find the node, then handle three cases. A leaf is unlinked. A node with one child is replaced by that child. A node with two children takes its inorder successor's value, and then the successor is deleted from the right subtree, which is one of the easy cases because the successor has no left child.

Floor, ceiling, and ranges

To find the largest value <= x, walk down as in a search and remember the last node where you went right. To list all values from low to high, walk in order but skip a left subtree when node.val < low and a right subtree when node.val > high.

Check that a tree is a BST

Pass the allowed range down: check(node, min, max) requires min <= node.val < max, then calls check(node.left, min, node.val) and check(node.right, node.val, max). Comparing only parent and child misses a deep value on the wrong side of a grandparent.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "BST", "sorted order", "k-th smallest", "closest value", "values in a range", or a stream of inserts mixed with "what's the nearest value" questions.
  • State the subtree rule, not the child rule: "everything left of a node is smaller, everything right is at least as big". Interviewers listen for this, because the child-only version leads to a wrong validator.
  • Before coding, decide out loud where duplicates go, and use that same rule in search, insert, and delete.
  • Expect "what if the inserts arrive sorted?". The tree becomes a chain and each operation is O(n). The fix is a self-balancing tree, such as an AVL or red-black tree, which keeps the height O(log n) with rotations.

Where frontend code uses it

The same idea in real UI code
  • JavaScript has no built-in sorted map. When an app needs ordered data that changes often, such as a timeline of events or price levels, libraries offer balanced search trees that keep values sorted under inserts.
  • VS Code's text buffer, called a piece tree, is stored in a balanced binary search tree so that finding the text at an offset follows one path down.
  • Range queries in a chart, such as "all points between these two timestamps", walk a search tree and skip every subtree that lies outside the range.

Related algorithms