Binary Search Trees
Quick reference
| search(root, target) | O(h) |
| insert(root, value) | O(h) |
| delete(root, value) | O(h) |
| findMin / findMax | O(h) |
| Inorder traversal | O(n) |
A binary search tree is a binary tree with one extra rule. For every node, everything in its left subtree is smaller than it, and everything in its right subtree is bigger. It is the same Node shape as the last topic, with the same left and right pointers. The only change is a promise about what those pointers mean.
That one rule turns the tree into a guessing game. Think about the number-guessing game. You pick a secret number, and every guess gets the answer "higher" or "lower", never the exact distance, only a direction. Each answer removes half of the range that was still possible. A BST plays this exact game with real data. At any node, you compare your target to node.value. This tells you which subtree to search next, and lets you ignore the other subtree completely, with no look at a single value inside it.
This is the halving idea, and it is new here. Nothing earlier in this course used it. A plain binary tree from the last topic has no such rule. So to find a value, you check nodes with no way to remove anything in advance. You might have to look at all of them. The ordering promise of a BST is what makes "ignore half of the tree" a safe move instead of a guess.
The node — same shape, new promise
structure Node:
value
left // -> Node, and every value in this subtree is < node.value
right // -> Node, and every value in this subtree is > node.value
// The ordering rule holds at every node, not only between a direct parent and child.search — compare, then go left or right
function search(node, target):
if node is NULL: // base case: reached the end of the tree, not found
return NULL
if target == node.value:
return node
if target < node.value:
return search(node.left, target) // remove the entire right subtree
return search(node.right, target) // remove the entire left subtreeinsert — navigate to the first empty spot, and place it there
function insert(node, value):
if node is NULL: // found an empty spot: this is where value belongs
return Node(value)
if value < node.value:
node.left = insert(node.left, value)
else if value > node.value:
node.right = insert(node.right, value)
return node // unchanged if value is already in the treedelete — three cases, by how many children the target has
function delete(node, value):
if node is NULL:
return NULL // value is not in the tree: nothing to do
if value < node.value:
node.left = delete(node.left, value)
else if value > node.value:
node.right = delete(node.right, value)
else:
// this is the node to remove
if node.left is NULL:
return node.right // leaf (both NULL) or one right child: splice it up
if node.right is NULL:
return node.left // one left child: splice it up
// two children: take the value of the in-order successor, then delete the successor
successor = findMin(node.right) // the smallest value in the right subtree
node.value = successor.value
node.right = delete(node.right, successor.value)
return nodefindMin / findMax — leftmost and rightmost node
function findMin(node):
while node.left is not NULL:
node = node.left
return node
function findMax(node):
while node.right is not NULL:
node = node.right
return nodevalidate — check the ordering rule with an inherited (min, max) range
function validate(node, min = -Infinity, max = +Infinity):
if node is NULL:
return true // an empty subtree cannot break any rule
if node.value <= min or node.value >= max:
return false
return validate(node.left, min, node.value) and validate(node.right, node.value, max)search, insert, and delete all walk one path from the root to some node. So all three cost O(h) time and O(h) recursion-stack space, where h is the height of the tree. This is O(log n) if the tree is balanced, and O(n) in the worst case if it is skewed (a direct callback to the skewed-tree edge case in Binary Trees). findMin and findMax walk the same kind of single path, but iteratively, so O(h) time and O(1) space, with no stack needed. Inorder traversal, inherited unchanged from Binary Trees, gets a new property here. On a BST, it visits every value in sorted order, for free, still O(n).
| Operation | Time | Space | Why |
|---|---|---|---|
| search(root, target) | O(h) | O(h) | One comparison per level, and one subtree discarded each time. This is O(log n) if balanced, and O(n) if the tree has become a chain. |
| insert(root, value) | O(h) | O(h) | This is the same navigation as search, continued one step further to the first empty spot. |
| delete(root, value) | O(h) | O(h) | To find the node is O(h). The two-children case adds one more O(h) walk to findMin and one more O(h) delete of the successor. This is still O(h) in total, not O(h²), because the successor search happens inside the height of the right subtree. |
| findMin / findMax | O(h) | O(1) | This is a plain iterative walk down one side of the tree. There is no recursion, so no stack frames build up. |
| Inorder traversal | O(n) | O(h) | This is the same traversal as Binary Trees, with every node visited one time. But the ordering rule of the BST means that left-root-right now visits every value from smallest to largest, with no sort step. |
Inserting already-sorted data degenerates into a linked list
Insert 1, 2, 3, 4, 5 in that order. 1 becomes the root. 2 is bigger, so it becomes the right child of 1. 3 is bigger than both, so it goes further right, and so on. Every node ends with only a right child, the exact skewed shape that Binary Trees warned about. search, insert, and delete all degrade from the expected O(log n) to O(n), because h is now equal to n. The BST gives you no protection against this on its own. To keep the tree balanced under sorted insertions needs extra machinery that this topic does not cover.
Deleting a two-children node without finding the true successor
The replacement for a deleted two-children node must be the smallest value in its right subtree, not just "some" nearby value, and not the right child itself unless that right child has no left child of its own. If you take the wrong node (for example, the right child directly, past its left subtree), the ordering rule breaks with no error. A later search for a value that is still in the tree can walk the wrong direction and report it missing.
Validating against only the immediate parent or children
A node can be bigger than its immediate left child and smaller than its immediate right child and still break the ordering rule against an ancestor further up. For example: the left grandchild of a right child must still be smaller than the original root, not only smaller than its own parent. A purely local, parent-to-child comparison misses violations like this completely. The (min, max) bound from the validate() in Build It catches it, because the bound accumulates from every ancestor, not only the nearest one.
Duplicate values with no consistent left-or-right rule
search, insert, and delete all depend on strict less-than and greater-than to pick a single direction. If duplicates are allowed, insert must pick one consistent side for equal values, always left or always right. Every other operation must agree with that same choice. If you pick inconsistently (some code paths send equal values left, others right), search can walk past a value that is actually in the tree, because it looked on the side that nothing agreed to use.
Sign in to mark problems done — progress syncs across devices.