Binary search trees (BST) explained

A binary search tree (BST) is a tree where every node has at most two children and the values are kept in order: every value hanging below a node on its left is smaller than that node, and every value below it on the right is larger. That rule means each comparison rules out half of what is left, so in a balanced tree you can search, insert or delete in O(log n) steps.

The binary search tree rule

Here is a BST built by inserting 41, 20, 65, 11, 29, 50, 91 and 32, in that order. The first value, 41, becomes the root. Nodes with no children, such as 11 and 32, are leaves.

        41
      /    \
    20      65
   /  \    /  \
  11  29  50  91
        \
        32

Pick any node and the rule holds. Everything left of 41 (20, 11, 29, 32) is smaller than 41, and everything to its right (65, 50, 91) is larger. The same is true for 20, for 65 and for every other node, so each subtree is a BST too.

Binary tree or binary search tree?

A binary tree is any tree where each node has at most two children. A binary search tree is a binary tree that also follows the ordering rule. All BSTs are binary trees, but a binary tree with 5 as the left child of 3 is not a BST.

Searching a binary search tree

1. Start at the root.
2. If the target equals this node, you have found it.
3. If the target is smaller, go left. If it is larger, go right.
4. Repeat. If you need to go to a child that does not exist, the value is not in the tree.

To find 32: compare with 41 (smaller, go left), 20 (larger, go right), 29 (larger, go right), then 32. That is 4 comparisons. To look for 55: 41 (go right), 65 (go left), 50 (go right), and 50 has no right child, so 55 is not there after just 3 comparisons.

Inserting into a binary search tree

Insertion is a search that fails on purpose. Follow the same left or right path as if you were looking for the new value, and when you reach an empty spot, put it there. A new value is always added as a leaf. Inserting 35 into the tree above goes 41, 20, 29, 32 and lands as the right child of 32.

Duplicates need a rule. Some trees ignore them, some keep a count in the node, and some send equal values to the right, as the code below does. Pick one and use it every time.

Deleting from a binary search tree

Find the node first. What happens next depends on how many children it has:

• No children: just remove it. Deleting 11 leaves 20 with only a right child.
• One child: connect the child to the deleted node's parent. Deleting 29 puts 32 in its place.
• Two children: replace its value with its in-order successor, the smallest value in its right subtree, then delete that successor, which has at most one child. Deleting 20 copies 29 into its place, then removes the old 29 by moving 32 up. The in-order predecessor, the largest value in the left subtree, works just as well.

Binary search tree traversal

Traversal means visiting every node once. There are three depth-first orders, named by when you visit the node itself compared with its subtrees.

Those uses are the ones the AQA A-level Computer Science specification lists, and you are expected to trace all three. In-order traversal of any BST gives the values sorted, which is a quick way to check a tree you have drawn.

Breadth-first traversal, which goes level by level (41, 20, 65, 11, 29, 50, 91, 32), uses a queue instead. The Search Algorithms course animates depth-first and breadth-first search side by side.

Time complexity: balanced and unbalanced

Every operation walks one path from the root, so it takes as many steps as the tree is tall. In a balanced tree each level doubles the number of nodes, so the height is about log₂ n. A million nodes fit in about 20 levels, because 2²⁰ = 1,048,576. That is why AQA gives binary tree search a time complexity of O(log n).

That only holds if the tree stays balanced. Insert values that are already sorted, such as 10, 20, 30, 40, and each one goes to the right of the last. The tree becomes a chain, and searching it is O(n), no better than a list. Self-balancing trees such as AVL trees and red-black trees fix this by rearranging nodes after each insert or delete, so the height stays O(log n).

Counting halvings is the skill behind all of this. Try one, then press Mark to check it in the course:

A binary search tree in JavaScript

This class inserts and searches without recursion. Paste it into the Code Editor to run it, then try inserting your own values.

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(value) {
    const node = new Node(value);
    if (!this.root) { this.root = node; return; }
    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) { current.left = node; return; }
        current = current.left;
      } else {
        if (!current.right) { current.right = node; return; }
        current = current.right;
      }
    }
  }

  contains(value) {
    let current = this.root;
    while (current) {
      if (value === current.value) return true;
      current = value < current.value ? current.left : current.right;
    }
    return false;
  }
}

function inOrder(node, out = []) {
  if (node) {
    inOrder(node.left, out);
    out.push(node.value);
    inOrder(node.right, out);
  }
  return out;
}

const tree = new BinarySearchTree();
[41, 20, 65, 11, 29, 50, 91, 32].forEach((v) => tree.insert(v));
console.log(tree.contains(32), tree.contains(55));   // true false
console.log(inOrder(tree.root).join(", "));          // 11, 20, 29, 32, 41, 50, 65, 91

Common mistakes

• Checking only a node's children. The rule covers the whole subtree. A node deep in the left subtree of 41 must still be smaller than 41.
• Assuming O(log n) always. That needs a balanced tree. Sorted input gives a chain and O(n).
• Mixing up pre-order and post-order. The name says when the node itself is visited: before its subtrees, or after them.
• Deleting a node with two children by moving one subtree up. Use the in-order successor or predecessor instead, or the ordering breaks.

Read next

Computer Science · CoursesSearch algorithms course: binary search, Big O, BFS and DFSAn interactive search algorithms course in 24 short sections: linear and binary search, Big O notation, hash tables, trees and graphs, and BFS vs DFS.