What Is a Binary Search Tree?

A binary search tree (BST) is a tree where each node has at most two children, with smaller values in the left subtree and larger values in the right. That ordering makes search, insert and delete O(log n) on a balanced tree.

The concept

To find a value, compare with the node: go left if smaller, right if larger. Each step discards half the remaining tree when balanced.

An in-order traversal visits values in sorted order. If you insert sorted data, an unbalanced BST degrades to a linked list (O(n)); self-balancing trees (AVL, Red-Black) prevent that.

Search for 6

Practical examples

Insert and search

class Node { constructor(v) { this.v = v; this.l = this.r = null } }
function insert(n, v) {
  if (!n) return new Node(v)
  v < n.v ? (n.l = insert(n.l, v)) : (n.r = insert(n.r, v))
  return n
}
function has(n, v) { return !n ? false : v === n.v ? true : has(v < n.v ? n.l : n.r, v) }

In-order traversal (sorted)

const inorder = (n) => n ? [...inorder(n.l), n.v, ...inorder(n.r)] : []

Height

const height = (n) => n ? 1 + Math.max(height(n.l), height(n.r)) : 0

Common mistakes

• Inserting sorted data into a plain BST.
• Forgetting duplicates policy.
• Deleting a node with two children incorrectly (use in-order successor).

Key takeaways

• Left smaller, right larger.
• O(log n) when balanced.
• In-order gives sorted output.

FAQ

BST vs hash table?

BST keeps order and supports range queries; hash tables are faster for exact lookups.

What are AVL and Red-Black trees?

Self-balancing BSTs that keep height logarithmic.