Binary Search Tree Insertion Tutorial

What Is Binary Search Tree Insertion?

Binary Search Tree insertion is the process of adding a new value to a Binary Search Tree while preserving its ordering property. Values smaller than a node are placed in its left subtree, while values greater than the node are placed in its right subtree.

Starting from the root, each comparison determines which subtree should contain the new value. The process continues until an empty child position is found.

BST Insertion Rule

Every insertion follows the same basic comparison:

If the new value is smaller than the current node, move left.
If the new value is greater than the current node, move right.
If the values are equal, follow the duplicate-value policy of the implementation.
When an empty position is reached, insert the new node there.

The same rule is applied recursively or iteratively until the correct position is found.

Inserting the First Value

If the tree is empty, the first inserted value becomes the root.

Insert 50:

    50

There is no comparison with another node because the tree does not contain a root yet.

Inserting a Smaller Value

Suppose the tree contains 50 and we want to insert 30. Since 30 is smaller than 50, it belongs in the left subtree.

Before:

    50

Insert 30:

    50
   /
  30

Inserting a Greater Value

If we insert 70 into the same tree, 70 is greater than 50, so it belongs in the right subtree.

      50
     /  \
   30    70

Step-by-Step BST Insertion

Consider inserting the following values in order:

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

The resulting tree is:

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

To insert 40, for example, compare it with 50 first. Since 40 is smaller, move left to 30. Then compare 40 with 30. Since 40 is greater, move right. The right child of 30 is empty, so 40 is inserted there.

Creating a BST Node

A simple JavaScript node contains a value and references to its left and right children.

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

Recursive BST Insertion

A recursive implementation follows the tree until it finds a null reference. At that point, a new node is created and returned to the parent.

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;
}

Notice that the recursive result is assigned back to either the left or right child. This is important when the subtree is initially empty and the newly created node needs to become that child.

Building a BST with Recursive Insertion

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);

Iterative BST Insertion

BST insertion can also be implemented without recursion. The iterative approach keeps moving through the tree until it finds an empty left or right child position.

function insert(root, value) {
  const newNode = new Node(value);

  if (root === null) {
    return newNode;
  }

  let current = root;

  while (true) {
    if (value < current.value) {
      if (current.left === null) {
        current.left = newNode;
        break;
      }

      current = current.left;
    } else if (value > current.value) {
      if (current.right === null) {
        current.right = newNode;
        break;
      }

      current = current.right;
    } else {
      break;
    }
  }

  return root;
}

Recursive vs Iterative Insertion

Both approaches preserve the same BST ordering rule. The main difference is how traversal state is maintained.

Aspect	Recursive	Iterative
Traversal	Recursive calls	Loop
Code size	Usually shorter	Usually more explicit
Extra space	O(h) call stack	O(1) auxiliary space
BST logic	Same	Same

Handling Duplicate Values

A BST implementation needs a clear policy for duplicate values. One common approach is to ignore a value when an equal value already exists.

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

Another implementation may consistently place duplicates on one side or store a frequency count in each node. The important requirement is consistency between insertion, search, and deletion.

Insertion into a Skewed BST

The order in which values are inserted affects the shape of a normal BST. Inserting already sorted values can create a highly skewed tree.

Insert:

10, 20, 30, 40, 50

Result:

10
  \
   20
     \
      30
        \
         40
           \
            50

In this situation, the tree behaves similarly to a linked list. Each insertion may need to travel through most of the existing nodes.

Insertion into a Balanced Shape

Inserting values in an order that produces a more balanced structure can reduce the height of the tree.

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

A normal BST does not automatically create this balance. If guaranteed balancing is required, self-balancing trees such as AVL Trees and Red-Black Trees can be used.

Insertion Complexity

BST insertion takes O(h) time, where h is the height of the tree. The actual complexity therefore depends on the shape of the tree.

Tree Shape	Insertion Time
Balanced BST	O(log n)
Typical / average case	O(log n)
Skewed BST	O(n)

Recursive insertion uses O(h) call-stack space. Iterative insertion uses O(1) auxiliary space apart from the newly allocated node.

Insertion and Inorder Traversal

One useful way to verify that insertion preserved the BST property is to perform an inorder traversal. A valid BST produces its values in sorted order.

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

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

  return result;
}

let root = null;

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

console.log(inorder(root));

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

Common BST Insertion Mistakes

Putting smaller values in the right subtree.
Putting larger values in the left subtree.
Forgetting to return the newly created root when inserting into an empty tree.
Failing to assign the recursive result back to the left or right child.
Handling duplicate values inconsistently.
Assuming a normal BST automatically remains balanced.
Ignoring the effect of insertion order on tree height.

BST Insertion vs Self-Balancing Insertion

In a normal BST, insertion only needs to preserve the ordering property. It does not perform rotations to maintain a particular height.

Self-balancing trees add additional work after insertion. AVL Trees use height-based balancing and rotations, while Red-Black Trees use node colors, recoloring, and rotations.

Structure	Insertion Behavior	Worst-Case Insertion
Binary Search Tree	Preserves ordering	O(n)
AVL Tree	Ordering + balancing	O(log n)
Red-Black Tree	Ordering + color balancing	O(log n)

Key Takeaways

BST insertion preserves the ordering relationship between nodes.
Smaller values move toward the left subtree.
Greater values move toward the right subtree.
The first value inserted becomes the root.
Insertion stops when an empty child position is found.
Duplicate handling should be explicitly defined.
Insertion takes O(h), where h is the tree height.
A balanced BST can provide O(log n) insertion.
A skewed BST can require O(n) insertion.
Normal BST insertion does not automatically rebalance the tree.

Topics

Binary Search Tree Insertion