Binary Search Tree (BST) Explained

Learn Binary Search Tree (BST) Explained with practical examples, explanations, best practices, and real-world coding techniques.

What Is a Binary Search Tree?

A Binary Search Tree (BST) is a binary tree that keeps its values in an ordered structure. For every node, values smaller than the node are stored in its left subtree, while values greater than the node are stored in its right subtree.

This ordering allows a Binary Search Tree to search for values by repeatedly choosing either the left or right subtree instead of visiting every node.

Binary Search Trees are commonly used to understand ordered data structures and form the foundation for more advanced structures such as AVL Trees and Red-Black Trees.

Binary Search Tree Structure

A Binary Search Tree consists of nodes connected through left and right child references. Each node can have zero, one, or two children. 

        50
       /  \
     30    70
    /  \  /  \
  20   40 60   80

In this example, values smaller than 50 are placed on the left and values greater than 50 are placed on the right. The same rule is applied recursively to every subtree.

BST Ordering Property

The most important rule of a Binary Search Tree is its ordering property:

  • Values in the left subtree are smaller than the node.
  • Values in the right subtree are greater than the node.
  • Both left and right subtrees must themselves follow the same BST property.

Some implementations allow duplicate values. When duplicates are supported, the program must define a consistent rule, such as always placing duplicates on the left or always placing them on the right.

Creating a BST Node

A basic JavaScript BST node can store a value and references to its left and right children. 

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

const root = new Node(50);

console.log(root.value);
console.log(root.left);
console.log(root.right);

Building a Binary Search Tree

A BST can be built by inserting values one at a time. The first value becomes the root. Each following value is compared with the current node and moved left or right until an empty position is found.

For example, inserting 50, 30, 70, 20, 40, 60, and 80 produces: 

        50
       /  \
     30    70
    /  \  /  \
  20   40 60   80

Searching in a Binary Search Tree

Searching is one of the main advantages of a BST. At each node, compare the target value with the current value.

  • If the values are equal, the target has been found.
  • If the target is smaller, continue in the left subtree.
  • If the target is greater, continue in the right subtree.
function search(root, value) {
  let current = root;

  while (current !== null) {
    if (value === current.value) {
      return current;
    }

    if (value < current.value) {
      current = current.left;
    } else {
      current = current.right;
    }
  }

  return null;
}

const root = new Node(50);
root.left = new Node(30);
root.right = new Node(70);

console.log(search(root, 30)?.value);

BST Insertion

To insert a new value, start at the root and compare the value with each node. Move left when the new value is smaller and right when it is greater. When an empty child position is reached, create the new node there. 

function insert(root, value) {
  if (root === null) {
    return new Node(value);
  }

  if (value < root.value) {
    root.left = insert(root.left, value);
  } else if (value > root.value) {
    root.right = insert(root.right, value);
  }

  return root;
}

let root = null;

root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 70);
root = insert(root, 20);
root = insert(root, 40);

console.log(root.value);

BST Insertion Example

Suppose the current tree contains 50, 30, and 70 and we want to insert 40. 

        50
       /  \
     30    70

Since 40 is smaller than 50, move left to 30. Since 40 is greater than 30, move right. The right child of 30 is empty, so 40 is inserted there. 

        50
       /  \
     30    70
       \
        40

BST Deletion

Deleting a node from a Binary Search Tree has three important cases. The correct approach depends on how many children the node has.

Case 1: Deleting a Leaf Node

A leaf node has no children. It can simply be removed from its parent. 

Before:

    50
   /
  30

Delete 30:

    50

Case 2: Node Has One Child

When a node has exactly one child, the node can be removed and its child connected directly to the node's parent. 

Before:

    50
   /
  30
    \
     40

Delete 30:

    50
   /
  40

Case 3: Node Has Two Children

Deleting a node with two children requires replacing its value with a suitable value from one of its subtrees. A common approach is to use the inorder successor, which is the smallest value in the node's right subtree. 

Before:

        50
       /  \
     30    70
          /  \
        60    80

Delete 70.

The inorder successor of 70 is 80.

After:

        50
       /  \
     30    80
          /
        60

Finding the Inorder Successor

The inorder successor of a node with a right subtree is the leftmost node in that right subtree. 

function findMin(root) {
  let current = root;

  while (current.left !== null) {
    current = current.left;
  }

  return current;
}

Complete BST Deletion Implementation

The following implementation handles leaf nodes, nodes with one child, and nodes with two children. 

function deleteNode(root, value) {
  if (root === null) {
    return null;
  }

  if (value < root.value) {
    root.left = deleteNode(root.left, value);
  } else if (value > root.value) {
    root.right = deleteNode(root.right, value);
  } else {
    // No left child
    if (root.left === null) {
      return root.right;
    }

    // No right child
    if (root.right === null) {
      return root.left;
    }

    // Two children
    const successor = findMin(root.right);
    root.value = successor.value;
    root.right = deleteNode(root.right, successor.value);
  }

  return root;
}

function findMin(root) {
  let current = root;

  while (current.left !== null) {
    current = current.left;
  }

  return current;
}

BST Traversals

Tree traversal is used to visit every node in a particular order. Binary Search Trees are especially useful for demonstrating the relationship between traversal order and sorted data.

Inorder Traversal

Inorder traversal visits the left subtree, the current node, and then the right subtree. For a valid BST, inorder traversal produces values in sorted order. 

function inorder(root) {
  if (root === null) {
    return;
  }

  inorder(root.left);
  console.log(root.value);
  inorder(root.right);
}

For the following tree: 

        50
       /  \
     30    70
    /  \  /  \
  20   40 60   80

The inorder traversal is: 

20, 30, 40, 50, 60, 70, 80

Preorder Traversal

Preorder traversal visits the current node first, followed by the left subtree and then the right subtree. 

function preorder(root) {
  if (root === null) {
    return;
  }

  console.log(root.value);
  preorder(root.left);
  preorder(root.right);
}

Postorder Traversal

Postorder traversal visits the left subtree, the right subtree, and then the current node. 

function postorder(root) {
  if (root === null) {
    return;
  }

  postorder(root.left);
  postorder(root.right);
  console.log(root.value);
}

Balanced vs Skewed BST

The performance of a Binary Search Tree depends heavily on its shape.

A reasonably balanced tree has a height close to logarithmic in the number of nodes: 

        40
       /  \
     20    60
    / \   / \
  10  30 50  70

In contrast, inserting already sorted values can create a highly skewed tree: 

10
  \
   20
     \
      30
        \
         40
           \
            50

In the skewed case, the BST loses much of the performance advantage of its ordering property.

BST Time Complexity

Search, insertion, and deletion depend on the height of the tree. If the tree is balanced, the height is approximately O(log n). If the tree becomes completely skewed, the height can become O(n).

Operation Average / Balanced Worst Case
Search O(log n) O(n)
Insertion O(log n) O(n)
Deletion O(log n) O(n)
Traversal O(n) O(n)
Space O(n) O(n)

BST Height and Performance

The key factor behind BST performance is its height. Searching does not depend directly on the total number of nodes; it depends on how many levels must be traversed to reach the target.

A balanced tree with many nodes can still provide efficient operations because each comparison eliminates a large portion of the remaining search space. A skewed tree may require visiting almost every node.

Advantages of Binary Search Trees

  • Maintains data in an ordered structure.
  • Supports efficient search when the tree is reasonably balanced.
  • Supports dynamic insertion and deletion.
  • Inorder traversal naturally produces sorted values.
  • Forms the foundation for several self-balancing tree structures.
  • Can be implemented without storing elements in a contiguous memory block.

Limitations of Binary Search Trees

  • A normal BST does not automatically maintain balance.
  • Sorted insertion can produce a skewed tree.
  • Worst-case search, insertion, and deletion can become O(n).
  • Deletion with two children requires additional logic.
  • Recursive implementations can become sensitive to tree height.

Binary Search Tree vs Binary Tree

A Binary Tree is any tree in which each node has at most two children. It does not necessarily maintain an ordering relationship between nodes.

A Binary Search Tree is a specialized binary tree that follows an ordering rule for its values.

Characteristic Binary Tree Binary Search Tree
Maximum children Two Two
Ordering requirement None Left < Node < Right
Sorted inorder traversal Not guaranteed Yes, for a valid BST
Efficient ordered search Not inherently supported Supported by the ordering property

Binary Search Tree vs AVL Tree

An AVL Tree is a self-balancing version of a Binary Search Tree. A normal BST can become skewed, while an AVL Tree performs rotations to maintain stricter height balance.

Red-Black Trees provide another approach to maintaining logarithmic height while allowing a different balance strategy.

Common BST Mistakes

  • Placing a smaller value in the right subtree.
  • Placing a greater value in the left subtree.
  • Forgetting that every subtree must also satisfy the BST property.
  • Ignoring duplicate-value behavior during insertion.
  • Handling only leaf deletion and forgetting the one-child and two-child cases.
  • Assuming every BST automatically has O(log n) operations.
  • Using inorder traversal without understanding why it produces sorted output.

Where Binary Search Trees Are Useful

Binary Search Trees are useful when data needs to remain ordered while supporting dynamic insertion, deletion, and lookup operations.

  • Learning ordered tree algorithms
  • Implementing searchable collections
  • Building sorted data structures
  • Understanding tree-based searching
  • Serving as a foundation for AVL and Red-Black Trees
  • Interview and algorithm problem solving

Key Takeaways

  • A Binary Search Tree is an ordered binary tree.
  • Values smaller than a node belong in its left subtree.
  • Values greater than a node belong in its right subtree.
  • Inorder traversal of a valid BST produces sorted values.
  • Search, insertion, and deletion depend on tree height.
  • A balanced BST can provide O(log n) operations.
  • A skewed BST can degrade to O(n) operations.
  • Deletion has separate cases for zero, one, and two children.
  • AVL Trees and Red-Black Trees extend the BST concept with self-balancing techniques.

Code Examples 

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

const root = new Node(50);
root.left = new Node(30);
root.right = new Node(70);

console.log(root.value);
console.log(root.left.value);
console.log(root.right.value);
    
function search(root, value) {
  let current = root;

  while (current !== null) {
    if (value === current.value) {
      return current;
    }

    if (value < current.value) {
      current = current.left;
    } else {
      current = current.right;
    }
  }

  return null;
}

const root = new Node(50);
root.left = new Node(30);
root.right = new Node(70);

const result = search(root, 30);

console.log(result ? result.value : "Not found");
    
class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function insert(root, value) {
  if (root === null) {
    return new Node(value);
  }

  if (value < root.value) {
    root.left = insert(root.left, value);
  } else if (value > root.value) {
    root.right = insert(root.right, value);
  }

  return root;
}

let root = null;

[50, 30, 70, 20, 40, 60, 80].forEach(value => {
  root = insert(root, value);
});

console.log(root.value);
    
function inorder(root, result = []) {
  if (root === null) {
    return result;
  }

  inorder(root.left, result);
  result.push(root.value);
  inorder(root.right, result);

  return result;
}

const root = new Node(50);
root.left = new Node(30);
root.right = new Node(70);
root.left.left = new Node(20);
root.left.right = new Node(40);

console.log(inorder(root));

Pro Tip

When working with a BST, always think in terms of the ordering rule: smaller values go left and greater values go right. If the tree becomes skewed, remember that a normal BST does not rebalance itself; self-balancing variants such as AVL and Red-Black Trees are designed for that purpose.

🎨 IgKnight Docs

Master HTML, CSS, JS, Python, .NET and more with easy-to-follow lessons and practical code examples.

© 2025 IgKnight Learning Platform. All rights reserved.