JS-201 · Lesson 9 of 12 · 30 min

Trees and binary search trees

▶ Video coming soon A video version of this lesson is on the way.

Lesson 6 met one tree already: the Food Hub's programs, with teams inside programs and groups inside teams. Trees are everywhere in software. The page you are reading is a tree of elements, the folders on a computer form a tree, and the index on a database table, as Theo showed in Databases and SQL for Applications, is a tree that keeps keys in order. At the ninth session, on Tuesday, October 5, Gareth turns to the kind of tree that makes ordered data fast: the binary search tree.

Tree vocabulary

A tree is a set of nodes connected by parent and child links, with one node at the top, the root, that has no parent. Every other node has exactly one parent. A node with no children is a leaf. A node together with everything beneath it is a subtree. The depth of a node is the number of links from the root to it, and the height of a tree is the greatest depth of any leaf. Because each node has only one parent, there is exactly one path from the root to any node, which is what separates a tree from the more general graphs of Lesson 10.

In a binary tree, each node has at most two children, called left and right. Binary trees are the basis of the structures in this lesson and of the heap in Lesson 4, which stored a binary tree in an array. Here the nodes are objects, each with a key and left and right references, exactly like linked list nodes with two next references instead of one.

Binary search trees

A binary search tree, or BST, is a binary tree that keeps one rule at every node: every key in the node's left subtree is smaller than the node's key, and every key in its right subtree is larger. That rule means a search can make the same decision as binary search at each node. Compare the target with the node's key: equal means found, smaller means go left, larger means go right. Each step goes one level down, so a search takes at most height + 1 steps.

A binary search tree of order numbers. The root is 50, with left child 30 and right child 70. 30 has children 20 and 40, and 40 has a left child 35. 70 has children 60 and 80. The search path for 35 is highlighted in green: 50, then left to 30, right to 40, left to 35.
A binary search tree after inserting 50, 30, 70, 20, 40, 60, 80 and 35. Searching for 35 follows one path down: four nodes.

Inserting follows the same path. Walk down from the root, going left or right by comparing keys, until the next step would be an empty child, and put the new node there. The tree in the figure was built by inserting 50, 30, 70, 20, 40, 60, 80 and 35 in that order.

JavaScript Example · Inserting and searching in a BST
class TreeNode {
  constructor(key) { this.key = key; this.left = null; this.right = null; }
}
class BST {
  constructor() { this.root = null; this.size = 0; }
  insert(key) {
    const node = new TreeNode(key);
    if (this.root === null) { this.root = node; this.size++; return; }
    let cur = this.root;
    for (;;) {
      if (key === cur.key) return;                     // no duplicates
      const side = key < cur.key ? 'left' : 'right';
      if (cur[side] === null) { cur[side] = node; this.size++; return; }
      cur = cur[side];
    }
  }
  has(key) {
    let cur = this.root, steps = 0;
    while (cur !== null) {
      steps++;
      if (key === cur.key) return { found: true, steps };
      cur = key < cur.key ? cur.left : cur.right;
    }
    return { found: false, steps };
  }
}

const orders = new BST();
for (const k of [50, 30, 70, 20, 40, 60, 80, 35]) orders.insert(k);
console.log('size', orders.size);
for (const k of [35, 50, 80, 45]) console.log(k, orders.has(k));
Output
size 8
35 { found: true, steps: 4 }
50 { found: true, steps: 1 }
80 { found: true, steps: 3 }
45 { found: false, steps: 3 }

What this code does

insert walks down from the root, choosing left for smaller keys and right for larger ones, and attaches the new node at the first empty place. has follows the same path and counts the nodes it visits. Finding 35 visits four nodes, and the missing key 45 is reported after three steps when the path runs out below 40.

Walking a tree in order

There are several standard orders for visiting every node of a binary tree, called traversals. In a preorder traversal, a node is visited before its subtrees; in postorder, after them; in inorder, between the left and right subtrees. A level-order traversal visits the root, then all nodes at depth 1, then depth 2, using a queue. All of them visit each node once, so all are O(n).

Inorder traversal of a BST has a special property: because everything smaller is on the left and everything larger on the right, visiting left subtree, node, right subtree lists the keys in sorted order. A BST is, in effect, a sorted list that also supports fast insertion.

JavaScript Example · Four ways to walk a tree
class TreeNode {
  constructor(key) { this.key = key; this.left = null; this.right = null; }
}
class BST {
  constructor() { this.root = null; this.size = 0; }
  insert(key) {
    const node = new TreeNode(key);
    if (this.root === null) { this.root = node; this.size++; return; }
    let cur = this.root;
    for (;;) {
      if (key === cur.key) return;                     // no duplicates
      const side = key < cur.key ? 'left' : 'right';
      if (cur[side] === null) { cur[side] = node; this.size++; return; }
      cur = cur[side];
    }
  }
  has(key) {
    let cur = this.root, steps = 0;
    while (cur !== null) {
      steps++;
      if (key === cur.key) return { found: true, steps };
      cur = key < cur.key ? cur.left : cur.right;
    }
    return { found: false, steps };
  }
}

function inorder(n, out = []) { if (n) { inorder(n.left, out); out.push(n.key); inorder(n.right, out); } return out; }
function preorder(n, out = []) { if (n) { out.push(n.key); preorder(n.left, out); preorder(n.right, out); } return out; }
function postorder(n, out = []) { if (n) { postorder(n.left, out); postorder(n.right, out); out.push(n.key); } return out; }
function levelOrder(root) {
  const out = [], queue = root ? [root] : [];
  for (let i = 0; i < queue.length; i++) {          // the array works as a queue with a head index
    const n = queue[i];
    out.push(n.key);
    if (n.left) queue.push(n.left);
    if (n.right) queue.push(n.right);
  }
  return out;
}

const t = new BST();
for (const k of [50, 30, 70, 20, 40, 60, 80, 35]) t.insert(k);
console.log('inorder:   ', inorder(t.root).join(' '));
console.log('preorder:  ', preorder(t.root).join(' '));
console.log('postorder: ', postorder(t.root).join(' '));
console.log('level order:', levelOrder(t.root).join(' '));
Output
inorder:    20 30 35 40 50 60 70 80
preorder:   50 30 20 40 35 70 60 80
postorder:  20 35 40 30 60 80 70 50
level order: 50 30 70 20 40 60 80 35

What this code does

The three recursive traversals differ only in where they record the node: before, between or after visiting its two subtrees. Inorder lists the keys of a BST in sorted order. levelOrder uses an array as a queue, reading it with an index that moves forward, so it visits the tree one level at a time.

Each order has uses. Preorder copies a tree or prints it as an outline, as Lesson 6's outline function did. Postorder handles children before parents, which is the right order for adding up totals or deleting a tree. Level order finds the nodes nearest the root first, which Lesson 10 develops into breadth-first search.

Smallest, largest and ranges

The smallest key in a BST is at the end of the path that always goes left, and the largest at the end of the path that always goes right. Both take O(height) steps. A range query, such as every booking number between 33 and 65, can skip whole subtrees: if a node's key is below the range, nothing in its left subtree can be in range either, so the search does not go there.

JavaScript Example · Minimum, maximum and a range query
class TreeNode {
  constructor(key) { this.key = key; this.left = null; this.right = null; }
}
class BST {
  constructor() { this.root = null; this.size = 0; }
  insert(key) {
    const node = new TreeNode(key);
    if (this.root === null) { this.root = node; this.size++; return; }
    let cur = this.root;
    for (;;) {
      if (key === cur.key) return;                     // no duplicates
      const side = key < cur.key ? 'left' : 'right';
      if (cur[side] === null) { cur[side] = node; this.size++; return; }
      cur = cur[side];
    }
  }
  has(key) {
    let cur = this.root, steps = 0;
    while (cur !== null) {
      steps++;
      if (key === cur.key) return { found: true, steps };
      cur = key < cur.key ? cur.left : cur.right;
    }
    return { found: false, steps };
  }
}

function min(t) { let n = t.root; while (n.left) n = n.left; return n.key; }
function max(t) { let n = t.root; while (n.right) n = n.right; return n.key; }
let visited = 0;
function range(n, lo, hi, out = []) {
  if (n === null) return out;
  visited++;
  if (lo < n.key) range(n.left, lo, hi, out);       // only go left if smaller keys could be in range
  if (lo <= n.key && n.key <= hi) out.push(n.key);
  if (n.key < hi) range(n.right, lo, hi, out);      // only go right if larger keys could be in range
  return out;
}

const t = new BST();
for (const k of [50, 30, 70, 20, 40, 60, 80, 35, 10, 25, 65, 90]) t.insert(k);
console.log('min', min(t), 'max', max(t));
console.log('33 to 65:', range(t.root, 33, 65), 'visited', visited, 'of', t.size, 'nodes');
Output
min 10 max 90
33 to 65: [ 35, 40, 50, 60, 65 ] visited 7 of 12 nodes

What this code does

min and max follow the left or right links until they run out. range visits a node's left subtree only when the range starts below the node's key, and its right subtree only when the range ends above it, so whole branches outside the range are skipped. The output is in sorted order because the recursion is an inorder traversal.

Removing a key

Deleting from a BST has three cases. A leaf can simply be removed. A node with one child can be replaced by that child, which moves the whole subtree up one level. A node with two children is the interesting case: replace its key with the key of its inorder successor, the smallest key in its right subtree, and then delete that successor node, which has at most one child. The replacement keeps the BST rule, because the successor is larger than everything on the left and smaller than everything else on the right.

JavaScript Example · Deleting from a BST
class TreeNode {
  constructor(key) { this.key = key; this.left = null; this.right = null; }
}
class BST {
  constructor() { this.root = null; this.size = 0; }
  insert(key) {
    const node = new TreeNode(key);
    if (this.root === null) { this.root = node; this.size++; return; }
    let cur = this.root;
    for (;;) {
      if (key === cur.key) return;                     // no duplicates
      const side = key < cur.key ? 'left' : 'right';
      if (cur[side] === null) { cur[side] = node; this.size++; return; }
      cur = cur[side];
    }
  }
  has(key) {
    let cur = this.root, steps = 0;
    while (cur !== null) {
      steps++;
      if (key === cur.key) return { found: true, steps };
      cur = key < cur.key ? cur.left : cur.right;
    }
    return { found: false, steps };
  }
}

function removeKey(node, key) {
  if (node === null) return null;
  if (key < node.key) node.left = removeKey(node.left, key);
  else if (key > node.key) node.right = removeKey(node.right, key);
  else {
    if (node.left === null) return node.right;      // no child or only a right child
    if (node.right === null) return node.left;      // only a left child
    let s = node.right;                             // two children: find the successor
    while (s.left) s = s.left;
    node.key = s.key;
    node.right = removeKey(node.right, s.key);
  }
  return node;
}
function inorder(n, out = []) { if (n) { inorder(n.left, out); out.push(n.key); inorder(n.right, out); } return out; }

const t = new BST();
for (const k of [50, 30, 70, 20, 40, 60, 80, 35]) t.insert(k);
t.root = removeKey(t.root, 20);   // a leaf
t.root = removeKey(t.root, 40);   // one child (35)
t.root = removeKey(t.root, 50);   // two children: replaced by 60
console.log('root', t.root.key, '| keys', inorder(t.root).join(' '));
Output
root 60 | keys 30 35 60 70 80

What this code does

removeKey walks down to the key and returns the updated subtree, so each parent can reattach whatever comes back. A node with at most one child is replaced by that child, and a node with two children takes its successor's key before the successor is removed from the right subtree. After removing 50, its successor 60 becomes the root, and the inorder listing confirms the keys are still in order.

Shape matters

Every BST operation costs O(height). For a tree that is well balanced, with roughly equal numbers of nodes on each side of every node, the height is about log₂ n, and search, insert and delete are all O(log n): about 20 steps for a million keys. But the shape depends entirely on the order of insertion. Insert keys in sorted order and each new key goes to the right of the last one; the tree becomes a single path, a linked list in disguise, with height n − 1, and every operation becomes O(n).

Two trees holding the keys 1 to 7. On the left, a balanced tree with root 4, children 2 and 6, and leaves 1, 3, 5 and 7, labeled height 2. On the right, a degenerate tree made by inserting 1 to 7 in order: each node has only a right child, forming a diagonal chain from 1 down to 7, labeled height 6.
The same seven keys in a balanced tree of height 2 and a degenerate tree of height 6.
JavaScript Example · Sorted inserts make a degenerate tree
class TreeNode {
  constructor(key) { this.key = key; this.left = null; this.right = null; }
}
class BST {
  constructor() { this.root = null; this.size = 0; }
  insert(key) {
    const node = new TreeNode(key);
    if (this.root === null) { this.root = node; this.size++; return; }
    let cur = this.root;
    for (;;) {
      if (key === cur.key) return;                     // no duplicates
      const side = key < cur.key ? 'left' : 'right';
      if (cur[side] === null) { cur[side] = node; this.size++; return; }
      cur = cur[side];
    }
  }
  has(key) {
    let cur = this.root, steps = 0;
    while (cur !== null) {
      steps++;
      if (key === cur.key) return { found: true, steps };
      cur = key < cur.key ? cur.left : cur.right;
    }
    return { found: false, steps };
  }
}

function height(n) { return n === null ? -1 : 1 + Math.max(height(n.left), height(n.right)); }
function lcg(seed) { return () => (seed = (seed * 48271) % 2147483647) / 2147483647; }

const n = 1023;
const sorted = new BST();
for (let k = 1; k <= n; k++) sorted.insert(k);

const rand = lcg(7);
const keys = Array.from({ length: n }, (_, i) => i + 1);
for (let i = keys.length - 1; i > 0; i--) { const j = Math.floor(rand() * (i + 1)); [keys[i], keys[j]] = [keys[j], keys[i]]; }
const shuffled = new BST();
for (const k of keys) shuffled.insert(k);

console.log('sorted inserts:   height', height(sorted.root), '| search for', n, 'takes', sorted.has(n).steps, 'steps');
console.log('shuffled inserts: height', height(shuffled.root), '| search for', n, 'takes', shuffled.has(n).steps, 'steps');
console.log('perfectly balanced height would be', Math.log2(n + 1) - 1);
Output
sorted inserts:   height 1022 | search for 1023 takes 1023 steps
shuffled inserts: height 21 | search for 1023 takes 8 steps
perfectly balanced height would be 9

What this code does

The first tree receives the keys 1 to 1,023 in sorted order, so it becomes one long chain and finding the largest key visits every node. The second receives the same keys in a shuffled order, made by a seeded generator so the result is repeatable, and its height is 21, more than the balanced ideal of 9 but fifty times less than the chain. Same keys, same code, very different costs, which is why balance matters.

Real data is often inserted in sorted or nearly sorted order: booking numbers increase, dates increase, ids increase. A plain BST is therefore risky in practice. Self-balancing trees fix this by rearranging nodes with small local moves called rotations after insertions and deletions, keeping the height O(log n) whatever the insertion order. The best known are AVL trees, which keep the heights of every node's two subtrees within one of each other, and red-black trees, which use a coloring rule that allows a little more imbalance in exchange for fewer rotations. Java's TreeMap and the C++ standard map are red-black trees.

Trees in the tools you use

JavaScript has no built-in ordered map or balanced tree, which surprises programmers coming from other languages. For most front-end work a sorted array with binary search, from Lesson 8, is fast enough, because insertions are rare compared with searches. When ordered data must change often, use a well-tested library rather than writing a balanced tree by hand.

Databases are where balanced trees do their heaviest work. The index Theo created on the shifts table in Databases and SQL for Applications is a B-tree, more precisely a B+ tree in most database engines. Instead of two children per node, each B-tree node holds hundreds of keys and has hundreds of children, sized to fit a block of disk or memory. A table of a million rows needs an index only three or four levels deep, so finding a row reads only a handful of blocks. That is the same idea as a balanced BST, adapted to storage where reading a block is expensive and comparing keys inside it is cheap.

Ways to keep and search a collection of keys.
StructureSearchInsertSorted listingNotes
Unsorted arrayO(n)O(1) at the endO(n log n), sort firstSimplest
Sorted arrayO(log n)O(n), elements moveO(n)Best for mostly reading
Plain BSTO(height)O(height)O(n) inorderHeight can reach n − 1
Balanced BST (AVL, red-black)O(log n)O(log n)O(n) inorderNot built in to JavaScript
B-tree indexO(log n), few blocksO(log n)O(n)Used by databases
Map or SetO(1) averageO(1) averageNot sortedInsertion order only

Mira notes one more tree from Gareth's list for later: the trie, or prefix tree, which stores strings letter by letter so that every word with a given prefix sits under one node. Search boxes with millions of entries use tries or similar structures for instant suggestions. For the Food Hub's few thousand names, the folded-name search from Lesson 8 is plenty.

Try it yourself

Tree height

Complete height(node) so that it returns the height of the tree rooted at node: -1 for an empty tree, 0 for a single node, and otherwise 1 more than the taller of its two subtrees.

The BST class is provided.

class TreeNode {
  constructor(key) { this.key = key; this.left = null; this.right = null; }
}
class BST {
  constructor() { this.root = null; this.size = 0; }
  insert(key) {
    const node = new TreeNode(key);
    if (this.root === null) { this.root = node; this.size++; return; }
    let cur = this.root;
    for (;;) {
      if (key === cur.key) return;                     // no duplicates
      const side = key < cur.key ? 'left' : 'right';
      if (cur[side] === null) { cur[side] = node; this.size++; return; }
      cur = cur[side];
    }
  }
  has(key) {
    let cur = this.root, steps = 0;
    while (cur !== null) {
      steps++;
      if (key === cur.key) return { found: true, steps };
      cur = key < cur.key ? cur.left : cur.right;
    }
    return { found: false, steps };
  }
}

function height(node) {
  if (node === null) return -1;
  return 0;
}

const t = new BST();
for (const k of [50, 30, 70, 20, 40, 35]) t.insert(k);
console.log(height(t.root), height(null), height(new TreeNode(1)));
const chain = new BST();
for (const k of [1, 2, 3, 4, 5]) chain.insert(k);
console.log(height(chain.root));

Try it yourself

Sorted booking numbers

Complete sortedKeys(node) so that it returns an array of all the keys in the BST in ascending order, using an inorder traversal.

Do not call sort.

class TreeNode {
  constructor(key) { this.key = key; this.left = null; this.right = null; }
}
class BST {
  constructor() { this.root = null; this.size = 0; }
  insert(key) {
    const node = new TreeNode(key);
    if (this.root === null) { this.root = node; this.size++; return; }
    let cur = this.root;
    for (;;) {
      if (key === cur.key) return;                     // no duplicates
      const side = key < cur.key ? 'left' : 'right';
      if (cur[side] === null) { cur[side] = node; this.size++; return; }
      cur = cur[side];
    }
  }
  has(key) {
    let cur = this.root, steps = 0;
    while (cur !== null) {
      steps++;
      if (key === cur.key) return { found: true, steps };
      cur = key < cur.key ? cur.left : cur.right;
    }
    return { found: false, steps };
  }
}

function sortedKeys(node) {
  if (node === null) return [];
  return [node.key];
}

const t = new BST();
for (const k of [41, 17, 63, 8, 29, 55, 72, 36]) t.insert(k);
console.log(sortedKeys(t.root).join(' '));
console.log(sortedKeys(null).length);

Try it yourself

Closest booking at or after a time

Complete ceiling(node, x) so that it returns the smallest key in the BST that is greater than or equal to x, or null if there is none. Walk down from the root without visiting every node.

When a node's key is at least x it is a candidate, and a smaller candidate can only be in its left subtree.

class TreeNode {
  constructor(key) { this.key = key; this.left = null; this.right = null; }
}
class BST {
  constructor() { this.root = null; this.size = 0; }
  insert(key) {
    const node = new TreeNode(key);
    if (this.root === null) { this.root = node; this.size++; return; }
    let cur = this.root;
    for (;;) {
      if (key === cur.key) return;                     // no duplicates
      const side = key < cur.key ? 'left' : 'right';
      if (cur[side] === null) { cur[side] = node; this.size++; return; }
      cur = cur[side];
    }
  }
  has(key) {
    let cur = this.root, steps = 0;
    while (cur !== null) {
      steps++;
      if (key === cur.key) return { found: true, steps };
      cur = key < cur.key ? cur.left : cur.right;
    }
    return { found: false, steps };
  }
}

function ceiling(node, x) {
  return null;
}

const t = new BST();
for (const k of [540, 480, 720, 600, 900, 660]) t.insert(k);   // shift start times in minutes
console.log(ceiling(t.root, 600), ceiling(t.root, 610), ceiling(t.root, 100), ceiling(t.root, 901));

Common mistakes

  • MistakeAssuming a BST is always O(log n).

    InsteadIts cost is O(height); sorted inserts make the height n − 1 and every operation O(n).

  • MistakeBreaking the BST rule by comparing only with the parent.

    InsteadEvery key in the left subtree must be smaller than the node, not just its direct child.

  • MistakeForgetting that deletion of a two-child node needs the successor.

    InsteadReplace the key with the smallest key in the right subtree, then delete that node.

  • MistakeWriting a balanced tree by hand for production code.

    InsteadUse a sorted array or a well-tested library; balanced trees are easy to get subtly wrong.

  • MistakeRecursing on a degenerate tree with thousands of nodes.

    InsteadThe recursion depth equals the height, so a chain can overflow the stack. Use loops for search and insert.

Summary and key terms

  • A tree has a root, parent and child links, leaves and subtrees, with exactly one path from the root to each node; depth counts links from the root and height is the greatest depth.
  • A binary tree gives each node at most a left and a right child.
  • A binary search tree keeps every left-subtree key smaller and every right-subtree key larger than the node, so search and insert follow one path down and cost O(height).
  • Preorder, inorder, postorder and level-order traversals each visit every node once, and inorder lists a BST's keys in sorted order.
  • Minimum and maximum follow the leftmost and rightmost paths, and range queries skip subtrees outside the range.
  • Deleting a node with two children uses its inorder successor.
  • Height is about log₂ n for a balanced tree but n − 1 for sorted insertions, so self-balancing AVL and red-black trees use rotations to keep it O(log n).
  • JavaScript has no built-in balanced tree.
  • Databases use B-trees with many keys per node, so indexes stay only a few levels deep.
tree
Nodes linked by parent and child links with one root and exactly one path to every node.
root
The top node of a tree, which has no parent.
leaf
A node with no children.
height
The number of links on the longest path from the root down to a leaf.
binary search tree
A binary tree in which left-subtree keys are smaller and right-subtree keys larger than each node's key.
inorder traversal
Visiting the left subtree, then the node, then the right subtree; it lists a BST in sorted order.
level-order traversal
Visiting a tree one depth at a time from the root, using a queue.
inorder successor
The next larger key in a BST, the smallest key in a node's right subtree.
balanced tree
A tree whose height stays close to log₂ n, keeping operations O(log n).
B-tree
A balanced tree with many keys per node, used for database indexes.

Practice problems

Work each problem on paper first, then reveal the answer to check.

  1. Which traversal of a BST gives its keys in ascending order?

    Show answer

    Inorder: left subtree, node, right subtree.

  2. What is the height of a BST built by inserting 1, 2, 3, ..., 100 in order?

    Show answer

    99, because every node has only a right child.

  3. Where is the smallest key in a BST?

    Show answer

    At the end of the path that always follows left children from the root.

  4. How is a node with two children deleted?

    Show answer

    Copy in its inorder successor's key, then delete the successor from the right subtree.

  5. Why are database indexes B-trees rather than binary trees?

    Show answer

    Each node holds many keys sized to a storage block, so the tree is very shallow and few blocks are read.

Lesson quiz · 5 questions

Score 60% or more to complete this lesson.

Take the quiz