AlgoViz
HomeBinary Search Trees

Introduction to BST

Easy

Left is smaller, right is bigger — everywhere

Problem

Learn the binary search tree: for every node, all left-subtree values are smaller and all right-subtree values are larger, giving O(log n) search.

In simple words

A sorted tree: smaller goes left, bigger goes right, so lookups halve each step.

The idea

In a binary search tree every value in a node's left subtree is smaller than the node and every value on the right is larger. That single invariant means a comparison at each node discards half the remaining tree, so search, insert and delete are all O(height).

The trick

  • The property is about whole subtrees, not just the immediate children.
  • An in-order traversal of a BST yields the values in sorted order.
  • O(log n) only when balanced; a sorted insertion order degrades it to a list.
5381479

Step 1 of 4. Search for 7. At each node go left if smaller, right if larger.

1/4
Optimal
timeO(h)spaceO(1)

Go left or right by comparison.

1function search(node, key) {2  while (node && node.val !== key)3    node = key < node.val ? node.left : node.right;4  return node;5}

Input

nodes
7, 6 edges

Output

found
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Example

Input:
insert 5,3,8,1,4
Output:
BST with 5 at root

Finished the walkthrough? Add it to your streak.