Overview#

A binary search tree (BST) is a data structure that adds a sorting constraint on top of a binary tree. It allows search, insertion, and deletion to proceed along the height of the tree rather than scanning every node.

The core property of a BST is:

1
All values in the left subtree < current node value < all values in the right subtree

If the tree stays balanced, the complexity of operations is close to O(log n); if it degenerates into a linked list, the complexity becomes O(n).

Prerequisites

• Binary tree: each node has at most a left and a right child
• Ordering: the left subtree is smaller than the root, the right subtree is larger than the root
• Recursive traversal: search, insertion, and validation all rely on recursing into subtrees

Problem Definition#

A BST is suitable for maintaining a set of comparable data and supporting dynamic search and updates.

Example:

1
      8
2
     / \
3
    3   10
4
   / \    \
5
  1   6    14

Path for searching 6:

1
6 < 8  -> go left
2
6 > 3  -> go right
3
6 = 6  -> found

BST problems usually revolve around four things:

Core Principle: Step-by-Step Diagram#

1
       8
2
      / \
3
   < 8   > 8

1
Left -> root -> right
2
1, 3, 6, 8, 10, 14

Detailed Algorithm Steps#

Inserting a value x:

1. If the current node is empty, create a new node;
2. If x < node.value, insert into the left subtree;
3. If x > node.value, insert into the right subtree;
4. If it equals the current value, decide based on business needs whether to ignore it, count it, or place it on one side;
5. Return the current node to keep the parent connection.

When validating a BST, you cannot just compare the current node with its left and right children. You must maintain a valid range:

1
min < node.value < max

When entering the left subtree, the upper bound becomes the current value; when entering the right subtree, the lower bound becomes the current value.

TypeScript Implementation#

1
class TreeNode {
2
  constructor(
3
    public value: number,
4
    public left: TreeNode | null = null,
5
    public right: TreeNode | null = null,
6
  ) {}
7
}

1
function searchBST(root: TreeNode | null, target: number): TreeNode | null {
2
  let current = root;
3

4
  while (current !== null) {
5
    if (target === current.value) return current;
6
    current = target < current.value ? current.left : current.right;
7
  }
8

9
  return null;
10
}

1
function insertIntoBST(root: TreeNode | null, value: number): TreeNode {
2
  if (root === null) return new TreeNode(value);
3

4
  if (value < root.value) {
5
    root.left = insertIntoBST(root.left, value);
6
  } else if (value > root.value) {
7
    root.right = insertIntoBST(root.right, value);
8
  }
9

10
  return root;
11
}

1
function isValidBST(root: TreeNode | null): boolean {
2
  function validate(node: TreeNode | null, min: number, max: number): boolean {
3
    if (node === null) return true;
4
    if (node.value <= min || node.value >= max) return false;
5

6
    return validate(node.left, min, node.value) && validate(node.right, node.value, max);
7
  }
8

9
  return validate(root, Number.NEGATIVE_INFINITY, Number.POSITIVE_INFINITY);
10
}

Engineering Optimization: Balance Determines Performance#

The ideal shape of a BST is close to balanced:

1
      4
2
    /   \
3
   2     6
4
  / \   / \
5
 1   3 5   7

In this case the height is O(log n). But if you insert in ascending order:

1
1 -> 2 -> 3 -> 4 -> 5

The tree degenerates into a linked list, and search becomes O(n).

In engineering, if you need stable ordered-set capabilities, you usually use balanced trees, skip lists, B-trees, or database indexes rather than a bare BST.

Applications and Limitations#

Summary#

• A BST adds the left-smaller-right-larger sorting constraint on top of a binary tree.
• In-order traversal of a BST yields an ascending sequence.
• The complexity of search, insertion, and deletion depends on the height of the tree.
• Validating a BST requires using upper and lower bounds, not just looking at direct children.
• In engineering, pay attention to balance, otherwise a BST will degenerate into a linked list.