Overview

A Binary Search Tree is a binary tree with an ordering rule: smaller values belong in the left subtree and larger values belong in the right subtree. This organization lets each comparison choose one branch and avoid unnecessary nodes.

Key concepts

• Every node has at most two children
• Left-subtree values are smaller than the node
• Right-subtree values are larger than the node
• Every subtree must follow the same BST rules

What is a Binary Search Tree?

A BST combines the branching structure of a binary tree with a consistent ordering rule.

         50
        /        30    70
     /     /    20  40  60  80

Every value to the left of 50 is smaller, every value to the right is larger, and the same rule holds within each subtree.

Why do we need a Binary Search Tree?

Searching a sorted phone directory does not require checking every page. You open near the middle and decide which half may contain the name. A BST uses the same idea: compare the target with a node and immediately choose the left or right branch.

Structure of a BST Node

Each node stores a value and references to its left and right children.

const node = {
  value: 50,
  left: null,
  right: null
};

console.log(node.value); // 50

Searching in a BST

To find 60, compare it with 50 and move right because it is larger. Compare it with 70 and move left because it is smaller. The next node is 60, so the search succeeds without visiting unrelated branches.

function searchBST(node, target) {
  if (node === null) {
    return false;
  }

  if (node.value === target) {
    return true;
  }

  if (target < node.value) {
    return searchBST(node.left, target);
  }

  return searchBST(node.right, target);
}

Inserting a new Node

Compare the new value with the current node, move left when smaller or right when larger, and insert it at the first empty child position.

function insertBST(node, value) {
  if (node === null) {
    return { value, left: null, right: null };
  }

  if (value < node.value) {
    node.left = insertBST(node.left, value);
  } else if (value > node.value) {
    node.right = insertBST(node.right, value);
  }

  return node;
}

For example, inserting 65 follows 50 → 70 → 60, then becomes the right child of 60. The BST ordering remains valid.

Deleting a Node

Deletion must preserve the ordering rule and has three cases.

• No children: remove the leaf
• One child: replace the node with its child
• Two children: replace the value with its inorder successor or predecessor, then delete that replacement node

Tree Traversal

BSTs support preorder, inorder, and postorder traversal. Inorder traversal is especially useful because it visits BST values in ascending order.

function inorder(node, values = []) {
  if (node === null) return values;

  inorder(node.left, values);
  values.push(node.value);
  inorder(node.right, values);

  return values;
}

// [20, 30, 40, 50, 60, 70, 80]

Time complexity

All core path-based operations take O(h), where h is tree height. AVL and Red-Black Trees automatically rebalance to keep height logarithmic.

Balanced and skewed Trees

Insertion order affects an ordinary BST. Inserting already sorted values can create a one-sided chain that behaves like a linked list. Balanced tree variants prevent this shape from becoming too tall.

Real-life example

A printed dictionary is alphabetically ordered. To find Computer, you open near the middle and decide whether to move earlier or later. A BST similarly eliminates one branch after every comparison.

Advantages of a BST

• Fast operations when balanced
• Maintains values in sorted order
• Supports efficient dynamic insertion and deletion
• Makes range and ordered traversal operations natural
• Forms the basis of advanced balanced trees

Limitations of a BST

• A poorly shaped tree can degrade to O(n)
• Performance depends on tree height
• Deletion has several structural cases
• Child references require additional memory

Where are Binary Search Trees used?

• Database indexes
• Search systems
• File management
• Contact applications
• Ordered dictionaries
• Memory management
• Compiler symbol tables

Tips for beginners

• Understand binary trees first
• Remember: smaller goes left, larger goes right
• Insert and search values manually
• Draw the tree after every change
• Practice inorder traversal
• Compare balanced and skewed shapes

Key takeaways

• A BST is an ordered binary tree
• Each node has at most two children
• Smaller values go left and larger values go right
• Balanced operations typically take O(log n)
• A skewed BST can degrade to O(n)
• Inorder traversal returns values in sorted order