Trees

Binary Search Trees

Written by Swapnil RajaUpdated 29 Aug 2026

A binary search tree is a sorted array that is cheap to insert into. Its whole advantage disappears the moment it becomes unbalanced, which happens on the most ordinary input there is: sorted data.

The one rule

For every node: everything in the left subtree is smaller, everything in the right subtree is larger. Applied recursively, at every node - not just the immediate children.

Search and insert

javascript

function search(node, target) {
  if (!node) return null
  if (node.value === target) return node

  // Half the tree is eliminated at every step.
  return target < node.value
    ? search(node.left, target)
    : search(node.right, target)
}

function insert(node, value) {
  if (!node) return new TreeNode(value)

  if (value < node.value) node.left = insert(node.left, value)
  else if (value > node.value) node.right = insert(node.right, value)

  return node   // equal values ignored
}

// TreeNode from the binary trees lesson.
class TreeNode {
  constructor(value) { this.value = value; this.left = null; this.right = null }
}

let demoRoot = null
for (const n of [2, 1, 3]) demoRoot = insert(demoRoot, n)
console.log(search(demoRoot, 3) !== null)  // true
console.log(search(demoRoot, 9) !== null)  // false

The trap that catches everyone

Validating a BST by comparing each node only to its children is wrong. The rule applies to the whole subtree, not the immediate child:

Wrong, then right

javascript

// WRONG — passes a tree that is not a BST.
function isValidWrong(node) {
  if (!node) return true
  if (node.left && node.left.value >= node.value) return false
  if (node.right && node.right.value <= node.value) return false
  return isValidWrong(node.left) && isValidWrong(node.right)
}

// RIGHT — carry the allowed range down.
function isValid(node, min = -Infinity, max = Infinity) {
  if (!node) return true
  if (node.value <= min || node.value >= max) return false

  return isValid(node.left, min, node.value)
      && isValid(node.right, node.value, max)
}

//     5
//    / \
//   3   7
//      / \
//     2   8      <- 2 is right of 5, so this is NOT a BST
// isValidWrong says true. isValid says false.

const demoTree = { value: 5, left: { value: 1, left: null, right: { value: 6, left: null, right: null } }, right: { value: 7, left: null, right: null } }
console.log(isValidWrong(demoTree))  // true — and wrong
console.log(isValid(demoTree))       // false — correct

Read that example carefully. The 2 is a valid left child of 7, but it sits in 5's right subtree where everything must exceed 5. Only the range-carrying version catches it.

Where it falls apart

Insert sorted data and every node goes right. The tree becomes a linked list and every operation degrades to O(n):

The degenerate case

javascript

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

function insert(node, value) {
  if (!node) return new TreeNode(value)
  if (value < node.value) node.left = insert(node.left, value)
  else if (value > node.value) node.right = insert(node.right, value)
  return node
}

let root = null
for (const n of [1, 2, 3, 4, 5]) root = insert(root, n)

// 1
//  \
//   2
//    \
//     3
//      \
//       4
//        \
//         5
// search(root, 5) now visits every node. O(n), not O(log n).

console.log("inserting sorted values builds a chain, not a balanced tree")

This is not a rare edge case - sorted input is extremely common. Self-balancing trees (AVL, red-black) exist entirely to prevent it, and they are what real libraries and databases use.

What to say when asked

Balanced - search, insert, delete all O(log n).
Degenerate - all O(n).
In-order traversal gives sorted output, which is the quickest validity check to describe.
In practice - a Map for exact lookup, a sorted array for ranges, a self-balancing tree only when you need both.

The property is recursive

Every value in the left subtree must be smaller than the node, and every value on the right larger - not just the immediate children. Checking only the children is the classic wrong answer to "validate a BST", and it accepts trees that are clearly invalid.

Validating with bounds

javascript

function isValidBST(node, min = -Infinity, max = Infinity) {
  if (!node) return true
  if (node.value <= min || node.value >= max) return false

  return (
    isValidBST(node.left, min, node.value) &&
    isValidBST(node.right, node.value, max)
  )
}

// The wrong version, for comparison: passes on invalid trees.
function looksValid(node) {
  if (!node) return true
  if (node.left && node.left.value >= node.value) return false
  if (node.right && node.right.value <= node.value) return false
  return looksValid(node.left) && looksValid(node.right)
}

const demoTree = { value: 5, left: { value: 1, left: null, right: { value: 6, left: null, right: null } }, right: { value: 7, left: null, right: null } }
console.log(isValidBST(demoTree))  // false
console.log(looksValid(demoTree))  // true — the naive check misses it

Each call narrows the permitted range. A node deep on the left of the root is still bounded above by the root's value, which is exactly what the naive check misses.

Why balance decides everything

A BST is O(log n) for search, insert and delete only while it is balanced. Insert already-sorted data and every node becomes a right child: the tree degenerates into a linked list and every operation becomes O(n).

Self-balancing variants - AVL, red-black - exist to prevent exactly that, and rotate on insert to keep the height logarithmic. You are rarely asked to implement one, but you are often asked why a plain BST is not enough.

PreviousBinary Trees Explained NextCommon Tree Problems