Binary Search Tree (BST)

A Binary Search Tree is a binary tree with one extra invariant: for every node N, all values in N's left subtree are strictly less than N.val, and all values in N's right subtree are strictly greater. This single rule makes search, insert, and delete all O(h) — where h is the tree height — and gives inorder traversal a powerful property: it visits every node in sorted ascending order.

The BST Property — Visual

Text

          8
        /   \
       3     10
      / \      \
     1   6      14
        / \    /
       4   7  13

For node 8:
  Left subtree  = {1, 3, 4, 6, 7}  -- all < 8  (check)
  Right subtree = {10, 13, 14}      -- all > 8  (check)

Inorder visit: 1 -> 3 -> 4 -> 6 -> 7 -> 8 -> 10 -> 13 -> 14  (sorted!)

Node Definition

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

Search — O(h)

At each node compare the target with node.val. Go left if target is smaller, right if larger, return the node on a match. Each step eliminates a whole subtree.

Recursive search

function search(node, target) {
  if (!node)            return null  // not found
  if (target === node.val) return node  // found
  if (target < node.val)
    return search(node.left, target)
  return search(node.right, target)
}

// Iterative — avoids call-stack depth issues on large trees
function searchIterative(root, target) {
  let cur = root
  while (cur) {
    if (target === cur.val) return cur
    cur = target < cur.val ? cur.left : cur.right
  }
  return null
}
// Time: O(h)   Space: O(h) recursive / O(1) iterative

Note

Average case h = O(log n) for a balanced tree; worst case h = O(n) for a sorted-insert (degenerate) tree. This is why self-balancing trees like AVL and Red-Black exist.

Insert — O(h)

Search for the correct empty spot, then attach a new leaf there. The BST invariant guarantees exactly one valid position for every new value.

function insert(root, val) {
  if (!root) return new TreeNode(val)  // found the empty spot
  if (val < root.val)
    root.left  = insert(root.left,  val)
  else if (val > root.val)
    root.right = insert(root.right, val)
  // val === root.val: duplicates ignored (common convention)
  return root
}

// Build the example tree: 8, 3, 10, 1, 6, 14, 4, 7, 13
let bst = null
for (const v of [8, 3, 10, 1, 6, 14, 4, 7, 13]) {
  bst = insert(bst, v)
}
// Time: O(h)   Space: O(h) call stack

Delete — Three Cases

Deletion is the trickiest BST operation. There are exactly three structural cases depending on how many children the target node has.

Case 1 — leaf node (no children)

Text

Delete 4 from:          Result:
      6                     6
     / \                   / \
    4   7                 _   7
Simply remove it.

Case 2 — one child

Text

Delete 10 from:         Result:
      8                     8
     / \                   / \
    3   10                3   14
          \              /
          14            13
         /
        13
Replace 10 with its only child (14).

Case 3 — two children (inorder successor)

Text

Delete 3 from:          Result:
      8                     8
     / \                   / \
    3   10                4   10
   / \                   / \
  1   6                 1   6
     / \                   / \
    4   7                 _   7

Inorder successor of 3 = smallest in right subtree = 4.
Copy 4's value into the node, then delete 4 from the right subtree.

Delete implementation

// Helper: find the minimum value node in a subtree
function minNode(node) {
  while (node.left) node = node.left
  return node
}

function deleteNode(root, val) {
  if (!root) return null

  if (val < root.val) {
    root.left  = deleteNode(root.left,  val)
  } else if (val > root.val) {
    root.right = deleteNode(root.right, val)
  } else {
    // Found the node to delete
    if (!root.left)  return root.right  // Case 1 or 2
    if (!root.right) return root.left   // Case 2

    // Case 3: two children
    // Replace value with inorder successor, then delete the successor
    const successor = minNode(root.right)
    root.val   = successor.val
    root.right = deleteNode(root.right, successor.val)
  }
  return root
}
// Time: O(h)   Space: O(h)

Inorder Gives Sorted Array

Because the BST property holds at every node, an inorder traversal (left, root, right) always visits nodes in ascending order. This is heavily exploited in interview problems.

function inorderSorted(root, result = []) {
  if (!root) return result
  inorderSorted(root.left,  result)
  result.push(root.val)
  inorderSorted(root.right, result)
  return result
}

inorderSorted(bst) // [1, 3, 4, 6, 7, 8, 10, 13, 14]

Validate BST

Checking only parent-child pairs is not enough — you must enforce that every node falls within a valid range inherited from its ancestors. Pass min/max bounds down the recursion.

Why naive check fails

Text

    5
   / \
  1   4      <- 4 < 5 seems ok locally
     / \
    3   6    <- but 3 < 5 violates the BST property!

Node 3 is in the right subtree of 5, so it must be > 5.
A local parent-child check misses this.

Validate BST with range bounds

function isValidBST(
  node,
  min = -Infinity,
  max = Infinity
) {
  if (!node) return true
  if (node.val <= min || node.val >= max) return false
  return (
    isValidBST(node.left,  min,       node.val) &&
    isValidBST(node.right, node.val,  max)
  )
}

isValidBST(bst) // true
// Time: O(n)   Space: O(h)

Kth Smallest Element

Inorder traversal visits nodes in ascending order, so the kth node visited is the kth smallest. Stop early once found.

function kthSmallest(root, k) {
  let count = 0
  let result = null

  function inorder(node) {
    if (!node || result !== null) return
    inorder(node.left)
    count++
    if (count === k) { result = node.val; return }
    inorder(node.right)
  }

  inorder(root)
  return result
}

kthSmallest(bst, 3) // 4  (sorted: 1,3,4,6,7,8,10,13,14)
// Time: O(h + k)   Space: O(h)

Tip

If kth-smallest is queried frequently on a mutable BST, augment each node with a subtree-size field. That turns each query into O(log n) — a classic follow-up in system-design interviews.

Lowest Common Ancestor (LCA) in BST

In a BST you can find the LCA without visiting every node. The LCA is the first node where the two target values diverge: p goes left and q goes right (or one of them equals the current node).

LCA of 4 and 7 in the example tree

Text

          8
        /   \
       3     10
      / \
     1   6
        / \
       4   7

At node 8: both 4 and 7 are < 8, go left.
At node 3: both 4 and 7 are > 3, go right.
At node 6: 4 < 6 and 7 > 6 => diverge here.
LCA(4, 7) = 6

function lowestCommonAncestor(root, p, q) {
  let cur = root
  while (cur) {
    if (p.val < cur.val && q.val < cur.val) {
      cur = cur.left         // both smaller: go left
    } else if (p.val > cur.val && q.val > cur.val) {
      cur = cur.right        // both larger: go right
    } else {
      return cur             // split point (or one equals cur)
    }
  }
  return null
}

// Time: O(h)   Space: O(1)

BST to Sorted Doubly Linked List (In-place)

Convert a BST to a circular sorted doubly linked list in-place by reusing left/right pointers as prev/next. Inorder traversal threads the nodes together.

Conversion idea

Text

BST inorder: 1 - 3 - 4 - 6 - 7 - 8 - 10 - 13 - 14

Doubly linked (circular):
<-> 1 <-> 3 <-> 4 <-> 6 <-> 7 <-> 8 <-> 10 <-> 13 <-> 14 <->
 ^                                                          ^
 |________________________ head __________________________|

function bstToDoublyLinkedList(root) {
  if (!root) return null

  let head = null  // first node (leftmost)
  let prev = null  // previously visited node

  function inorder(node) {
    if (!node) return
    inorder(node.left)

    // Link prev <-> node
    if (prev) {
      prev.right = node
      node.left  = prev
    } else {
      head = node  // leftmost node becomes head
    }
    prev = node

    inorder(node.right)
  }

  inorder(root)

  // Make it circular: head <-> tail
  prev.right = head
  head.left  = prev

  return head
}
// Time: O(n)   Space: O(h)

Complexity Reference

Operation	Average (balanced)	Worst (skewed)	Notes
Search	O(log n)	O(n)	Iterative avoids stack overhead
Insert	O(log n)	O(n)	New value always becomes a leaf
Delete	O(log n)	O(n)	Three cases; successor for 2-child
Kth Smallest	O(log n + k)	O(n)	Stop early in inorder
LCA	O(log n)	O(n)	Only in BST; general tree is O(n)
Validate	O(n)	O(n)	Must check every node
Inorder Sort	O(n)	O(n)	Always visits all nodes

Common BST Interview Patterns

Inorder traversal = sorted order — exploit this for kth-smallest, range queries, and conversion problems
Range bounds for validation — always pass (min, max) down; never just compare parent-child
LCA divergence rule — when p and q land on different sides of a node, that node is the LCA
Deletion Case 3 — replace with inorder successor (min of right subtree), then delete the successor
Height matters — mention self-balancing (AVL, Red-Black) when the interviewer asks about worst-case
Augmented BST — add a subtree-count field to answer kth-smallest in O(log n)

Interview Problem — Range Sum of BST

Sum all node values in the range [low, high] inclusive. Prune branches that cannot possibly contribute.

function rangeSumBST(root, low, high) {
  if (!root) return 0

  let sum = 0

  // Only visit root if it might be in range
  if (root.val >= low && root.val <= high) {
    sum += root.val
  }
  // Prune: no need to go left if root.val <= low
  if (root.val > low) {
    sum += rangeSumBST(root.left,  low, high)
  }
  // Prune: no need to go right if root.val >= high
  if (root.val < high) {
    sum += rangeSumBST(root.right, low, high)
  }
  return sum
}

rangeSumBST(bst, 4, 10) // 4+6+7+8+10 = 35
// Time: O(n) worst case, much better in practice with pruning

Interview Problem — Convert Sorted Array to BST

Given a sorted array, build a height-balanced BST. Always pick the middle element as the root so both subtrees are equal in size.

function sortedArrayToBST(nums) {
  function build(lo, hi) {
    if (lo > hi) return null
    const mid  = Math.floor((lo + hi) / 2)
    const node = new TreeNode(nums[mid])
    node.left  = build(lo,      mid - 1)
    node.right = build(mid + 1, hi)
    return node
  }
  return build(0, nums.length - 1)
}

sortedArrayToBST([1, 3, 4, 6, 7, 8, 10, 13, 14])
//         7
//       /   \
//      3    10
//     / \  /  \
//    1  4 8   13
//        \ \    \
//         6  9  14
// Time: O(n)   Space: O(log n)

Warning

A BST built by inserting a sorted array one element at a time produces a completely right-skewed tree (h = n). Always build from a sorted array using the middle-element approach for a balanced result.

Quick Reference

BST invariant: left subtree values < node < right subtree values (strict inequality)
Inorder traversal of BST always yields sorted ascending output
Search, insert, delete: O(h) — O(log n) balanced, O(n) degenerate
Validate with range bounds (min/max), not just parent-child comparison
LCA in BST: O(h) — the first node where p and q diverge
Kth smallest: inorder traversal, stop at kth visit
BST to sorted DLL: inorder threading, reuse left/right as prev/next
Always mention balanced BSTs (AVL, Red-Black) when asked about guarantees