TreesLesson 2

Binary Search Trees

Left child smaller, right child larger. How to search, insert, and delete in a BST — with step-by-step visual walkthroughs.

What Is It?

A Binary Search Tree (BST) is a binary tree with one simple rule: for every node, everything to its left is smaller, and everything to its right is bigger.

This rule applies at every single node, not just the top. Because of it, you can search the tree very efficiently — at each step, you eliminate half the remaining possibilities.

Search, insert, and delete all take O(h) time, where h is the height of the tree. When the tree is balanced and short, h = log(n), which is fast. When the tree is tall and lopsided, h = n, which is slow.

Analogy

The 20 Questions Game

Imagine guessing a number between 1 and 100. Each time you guess, you're told "higher" or "lower."

A smart player starts at 50. If the answer is higher, they guess 75. If then lower, they guess 63. Every guess cuts the remaining range in half.

A BST works the same way. At each node, you compare your target with the node's value. Too small? Go left. Too big? Go right. Each step cuts out an entire half of the tree.

But here's the catch: this only works well if the tree is balanced — like a fair game where each guess really does cut the range in half. A lopsided tree is like a guessing game where the answers always say "higher" — you end up checking every number one by one.

How It Works

The BST Rule

For every node in the tree:

  • All nodes in its LEFT subtree have values that are smaller
  • All nodes in its RIGHT subtree have values that are bigger
pseudocode
1
2
3
4
5
6
7
8
         Valid BST              NOT a valid BST
            8                        8
           / \                      / \
          3   10                   3   10
         / \    \                 / \    \
        1   6   14               1   9   14
           / \  /                   / \  /
          4  7 13                  4  7 13

The right tree is invalid because 9 is in the left subtree of 8 but is greater than 8. The rule applies to ALL descendants, not just direct children.

SEARCH

Start at the root. Compare. Go left or right. Repeat until found or you hit null.

pseudocode
1
2
3
4
5
6
7
8
9
function search(node, target):
    if node is null:
        return null              // Not found
    if target == node.data:
        return node              // Found!
    if target < node.data:
        return search(node.left, target)   // Go left
    else:
        return search(node.right, target)  // Go right

Searching for 6:

pseudocode
1
2
3
4
5
6
7
         8          6 < 8, go left
        / \
       3   10       6 > 3, go right
      / \
     1   6          6 == 6, FOUND!
        / \
       4   7

Only 3 comparisons to find the node. That's fast.

INSERT

Insertion works just like search. Follow the path until you hit a null spot. That's where the new node goes. New nodes always become leaves.

pseudocode
1
2
3
4
5
6
7
8
function insert(node, value):
    if node is null:
        return new TreeNode(value)    // Place it here
    if value < node.data:
        node.left = insert(node.left, value)
    else if value > node.data:
        node.right = insert(node.right, value)
    return node

Inserting 5:

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Step 1:  8     5 < 8, go left
​
Step 2:  3     5 > 3, go right
​
Step 3:  6     5 < 6, go left
​
Step 4:  4     5 > 4, go right
​
Step 5:  null  Place 5 here!
​
Result:
            8
           / \
          3   10
         / \
        1   6
           /
          4
           \
            5   <-- new leaf

DELETE — The Tricky One

Deletion has three cases depending on how many children the node has.

Case 1: Node is a leaf (no children). Just remove it.

pseudocode
1
2
3
4
5
6
7
8
Delete 4:
      8                 8
     / \               / \
    3   10    -->     3   10
   / \               / \
  1   6             1   6
     /
    4  <-- remove

Case 2: Node has one child. Replace the node with its only child.

pseudocode
1
2
3
4
5
6
7
8
Delete 10 (has one child: 14):
      8                 8
     / \               / \
    3   10    -->     3   14
   / \    \          / \  /
  1   6   14        1   6 13
         /
        13

Case 3: Node has two children. Find the inorder successor — the smallest value in the right subtree. Copy that value into the node being deleted, then delete the inorder successor (which is guaranteed to have at most one child).

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Delete 3 (has two children: 1 and 6):
           8
          / \
         3   10        Inorder successor of 3 = 4
        / \    \       (smallest value in right subtree of 3)
       1   6   14
          /
         4
​
Step 1: Copy 4 into the node that had 3
           8
          / \
         4   10
        / \    \
       1   6   14
          /
         4     <-- now delete this copy (it's a leaf)
​
Step 2: Delete the original 4 (Case 1 — leaf)
           8
          / \
         4   10
        / \    \
       1   6   14
​
BST property is preserved!

The full delete code:

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function delete(node, value):
    if node is null:
        return null
    
    if value < node.data:
        node.left = delete(node.left, value)
    else if value > node.data:
        node.right = delete(node.right, value)
    else:
        // Found the node to delete
        if node.left is null and node.right is null:
            return null                        // Case 1: leaf
        if node.left is null:
            return node.right                  // Case 2: one child
        if node.right is null:
            return node.left                   // Case 2: one child
        
        // Case 3: two children
        successor = findMin(node.right)
        node.data = successor.data
        node.right = delete(node.right, successor.data)
    
    return node
​
function findMin(node):
    while node.left is not null:
        node = node.left
    return node

Balanced vs. Degenerate BSTs

The speed of a BST depends entirely on its shape. The same values can produce a fast or slow BST depending on the order you insert them.

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
BALANCED (h = log n)         DEGENERATE (h = n)
Insert: 4, 2, 6, 1, 3, 5, 7  Insert: 1, 2, 3, 4, 5, 6, 7
​
        4                     1
       / \                     \
      2   6                     2
     / \ / \                     \
    1  3 5  7                     3
                                   \
    Height: 2                       4
    Search: O(log n)                 \
                                      5
                                       \
                                        6
                                         \
                                          7
                                  Height: 6
                                  Search: O(n)

Same 7 values. But inserting them in sorted order creates a straight line — basically a linked list. Every search has to check every node.

This is why balanced BSTs (like AVL trees and Red-Black trees) exist — they automatically reorganize after each insertion. But that's for another lesson.

Time Complexity Summary

Search
O(n)degenerate
Insert
O(n)degenerate
Delete
O(n)degenerate
Min/Max
O(n)degenerate

All operations are O(h). h ranges from log(n) for a balanced tree to n for a degenerate one.

Finding Min and Max

The minimum is always the leftmost node. The maximum is always the rightmost node.

pseudocode
1
2
3
4
5
6
7
8
9
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 node

Examples

Example 1: Building a BST step by step

Insert: 8, 3, 10, 1, 6, 14

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Insert 8:    8
​
Insert 3:    8          Insert 10:   8
            /                       / \
           3                       3   10
​
Insert 1:    8          Insert 6:    8
            / \                     / \
           3   10                  3   10
          /                       / \
         1                       1   6
​
Insert 14:   8
            / \
           3   10
          / \    \
         1   6   14

Example 2: Inorder traversal gives sorted output

A BST has a useful property: if you visit nodes in left-node-right order (called inorder), you get all values in sorted order.

pseudocode
1
2
3
4
5
6
7
8
9
         8
        / \
       3   10
      / \    \
     1   6   14
        / \
       4   7
​
Inorder: 1, 3, 4, 6, 7, 8, 10, 14  (sorted!)

Example 3: Validating a BST

You can't just check each node against its direct children. You must pass down the allowed range.

pseudocode
1
2
3
4
5
6
7
8
9
function isValidBST(node, minVal, maxVal):
    if node is null:
        return true
    if node.data <= minVal or node.data >= maxVal:
        return false
    return isValidBST(node.left, minVal, node.data) and
           isValidBST(node.right, node.data, maxVal)
​
// Call with: isValidBST(root, -INFINITY, +INFINITY)

Common Mistakes

  1. Checking only direct children for the BST property. The BST rule applies to ALL descendants. A left child's right subtree might have a value that's too large. Use min/max bounds when validating.
  1. Forgetting to reassign after deletion. The delete function returns the modified subtree. You must assign it back: node.left = delete(node.left, value). Without this, the tree isn't actually changed.
  1. Getting the two-children delete case wrong. Copy the successor's VALUE into the node, then delete the successor from its original spot. Don't delete the successor first — you'd lose its value.
  1. Assuming BSTs are always balanced. Inserting already-sorted values (1, 2, 3, 4...) creates a worst-case tree. Always consider this.

Best Practices

  • Use recursion for search, insert, and delete — it naturally mirrors the tree's structure
  • Always test edge cases: empty tree, single node, deleting the root, inserting a duplicate
  • If you need guaranteed fast operations, use a self-balancing BST — a plain BST can degenerate
  • Remember that inorder traversal of a BST gives sorted order — this is useful for many problems

Runnable Code

Here is a complete JavaScript BST implementation you can run. It covers insert, search, delete, and all four traversal methods (inorder, preorder, postorder, BFS level-order).

js
Binary Search Tree — Full Implementation with Traversals
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
class TreeNode {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}
​
class BST {
  constructor() {
    this.root = null;
  }
​
  insert(data) {
    this.root = this._insert(this.root, data);
  }
  _insert(node, data) {
    if (!node) return new TreeNode(data);
    if (data < node.data) node.left = this._insert(node.left, data);
    else if (data > node.data) node.right = this._insert(node.right, data);
    return node;
  }
​
  search(data) {
    return this._search(this.root, data);
  }
  _search(node, data) {
    if (!node) return false;
    if (data === node.data) return true;
    if (data < node.data) return this._search(node.left, data);
    return this._search(node.right, data);
  }
​
  delete(data) {
    this.root = this._delete(this.root, data);
  }
  _delete(node, data) {
    if (!node) return null;
    if (data < node.data) { node.left = this._delete(node.left, data); return node; }
    if (data > node.data) { node.right = this._delete(node.right, data); return node; }
    // Found the node
    if (!node.left && !node.right) return null;
    if (!node.left) return node.right;
    if (!node.right) return node.left;
    // Two children: find inorder successor
    let successor = node.right;
    while (successor.left) successor = successor.left;
    node.data = successor.data;
    node.right = this._delete(node.right, successor.data);
    return node;
  }
​
  // DFS: Left -> Node -> Right (sorted order)
  inorder(node = this.root, result = []) {
    if (node) {
      this.inorder(node.left, result);
      result.push(node.data);
      this.inorder(node.right, result);
    }
    return result;
  }
​
  // DFS: Node -> Left -> Right
  preorder(node = this.root, result = []) {
    if (node) {
      result.push(node.data);
      this.preorder(node.left, result);
      this.preorder(node.right, result);
    }
    return result;
  }
​
  // DFS: Left -> Right -> Node
  postorder(node = this.root, result = []) {
    if (node) {
      this.postorder(node.left, result);
      this.postorder(node.right, result);
      result.push(node.data);
    }
    return result;
  }
​
  // BFS: Level order traversal
  bfs() {
    if (!this.root) return [];
    const result = [];
    const queue = [this.root];
    while (queue.length > 0) {
      const node = queue.shift();
      result.push(node.data);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    return result;
  }
}
​
// --- Demo ---
const bst = new BST();
[8, 3, 10, 1, 6, 14, 4, 7].forEach(v => bst.insert(v));
console.log('BST built with: 8, 3, 10, 1, 6, 14, 4, 7');
console.log('');
console.log('--- Traversals ---');
console.log('Inorder (sorted):', bst.inorder().join(', '));
console.log('Preorder:         ', bst.preorder().join(', '));
console.log('Postorder:        ', bst.postorder().join(', '));
console.log('BFS (level order):', bst.bfs().join(', '));
console.log('');
console.log('--- Search ---');
console.log('Search 6:', bst.search(6) ? 'found' : 'not found');
console.log('Search 5:', bst.search(5) ? 'found' : 'not found');
console.log('');
console.log('--- Delete ---');
bst.delete(3);
console.log('After deleting 3 (two children):');
console.log('Inorder:', bst.inorder().join(', '));
bst.delete(14);
console.log('After deleting 14 (leaf):');
console.log('Inorder:', bst.inorder().join(', '));
What Is a Tree?Tree Traversals — DFS