Binary search trees

A binary search tree (BST) keeps its keys in order: everything to the left of a node is smaller, everything to the right is greater or equal. This rule lets you search, insert and delete by following a single path from the root.

The ordering property

For every node x:

every key in the left subtree is ≤ x.key;
every key in the right subtree is ≥ x.key.

Careful: the rule applies to the whole subtree, not just the direct children. A tree where each left child is smaller than its parent is not necessarily a BST.

The examples below use this tree:

        50
      /    \
    30      70
   /  \    /  \
  20  40  60  80

Search and insertion

Start at the root. If the value is smaller than the current node, go left; otherwise, go right. To insert, walk down the same way until you hit a NULL pointer, and attach the new node there.

Example: insert 45. 45 < 50 → left; 45 ≥ 30 → right; 45 ≥ 40 → right; NULL. 45 becomes the right child of 40.

insert(root, v):
    if root == NULL: return new Node(v)
    if v < root.key: root.left  = insert(root.left, v)
    else:            root.right = insert(root.right, v)
    return root

Deletion: three cases

Leaf: simply remove it.
One child: the child takes the node's place.
Two children: copy into the node the value of its predecessor (the largest key of the left subtree), then delete the old predecessor. It never has a right child, so we fall back to case 1 or 2.

Example: delete 50 from the tree above. Its predecessor is 40 (go left once, then right all the way). Copy 40 into the root, then remove the old leaf 40.

You could also use the successor (the smallest key of the right subtree). Both methods are correct; this site follows the predecessor convention.

Successor and predecessor

Successor of x: if x has a right subtree, it is the minimum of that subtree. It is not necessarily the right child. The successor of 50 is 60, not 70.
Predecessor of x: if x has a left subtree, it is the maximum of that subtree. The predecessor of 50 is 40, not 30.
If x has no subtree on the right side, you have to go up through its ancestors.

Traversals

Traversal	Order	On the example tree
Preorder	root, left, right	50, 30, 20, 40, 70, 60, 80
In-order	left, root, right	20, 30, 40, 50, 60, 70, 80
Postorder	left, right, root	20, 40, 30, 60, 80, 70, 50

The in-order traversal of a BST always yields the keys in sorted order. It is a good way to check that a tree respects the ordering property.

Rebuilding a tree from two traversals

With the in-order and postorder (or preorder) traversals, you can rebuild the tree. The last element of the postorder is the root. Find it in the in-order traversal: what is on its left forms the left subtree, what is on its right forms the right subtree. Repeat recursively on each half.

Finding the k-th smallest element

If every node stores the size of its subtree, the k-th smallest element can be found without visiting the whole tree. At the current node, its rank within the subtree is r = size(left) + 1:

if k = r, it is this node;
if k < r, go left with the same k;
if k > r, go right with k − r.

Example: the 6th smallest of the example tree. At 50, r = 3 + 1 = 4 and 6 > 4: go right with k = 2. At 70, r = 1 + 1 = 2 = k: the answer is 70.

Keeping these sizes up to date costs O(1) per modified node, so insertion and deletion stay O(h).

Complexity

Operation	Balanced tree	Worst case (degenerate tree)
Search, insertion, deletion	O(log n)	O(n)
Full traversal	O(n)	O(n)

The worst case happens when you insert already sorted values: the tree turns into a line. That is exactly the problem red-black trees solve.