Binary Search Tree

Insertion

What is BST Insertion?

A Binary Search Tree keeps every node's left subtree smaller and its right subtree larger, and insertion is what builds that ordering up one value at a time. To insert a new value, you walk down from the root exactly the way you'd search for it — go left when the value is smaller, go right when it's larger — and the moment you fall off the tree (hit a null pointer), that's where the new node gets attached.

How Does It Work?

  1. Insert 5 into a tree rooted at 8
  2. 8: 5 < 8 → go left
  3. 3: 5 > 3 → go right
  4. 6: 5 < 6 → go left
  5. Left of 6 is empty → attach 5 here as a new leaf
8310165
Comparison pathNewly inserted node

Because every insertion is really just a failed search, the new node always becomes a leaf. Nothing above it has to move or shift — inserting into a BST never requires shuffling existing nodes around, only adding one new connection at the bottom.

Algorithm Steps

  1. Start at the root
  2. Compare the new value with the current node:
    • If smaller, move to the left child
    • If larger, move to the right child
    • If equal, stop (duplicate — most BSTs ignore or reject it)
  3. Repeat until you reach a null (empty) pointer
  4. Attach the new node there as a leaf

Time Complexity

  • Best/Average Case: Roughly balanced tree → O(log n).
  • Worst Case: Degenerate/skewed tree → O(n).

Time Complexity Analysis

Advertisement

Space Complexity

Insertion needs O(1) extra space beyond the recursion stack, since it only ever creates a single new node.

The shape you end up with depends entirely on insertion order. Insert already-sorted data and you get a degenerate, linked-list-shaped tree (see Binary Tree Types) with Θ(n) height. Insert in a randomized order and the tree tends to stay close to balanced, keeping height near Θ(log n) — this is exactly why self-balancing trees like AVL exist.

Daily DSA Challenge by Scale Engineer

Insert values and watch the comparison path light up before each node lands

Tree is empty
No tree yet — insert a value or generate a random tree
Internal nodeLeaf nodeRootComparison path

Test Your Knowledge before moving forward!

BST Insertion Quiz

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • -0.5 point penalty for viewing explanations
  • Earn stars based on your final score (max 5 stars)

Binary Search Tree Insertion Implementation

// Binary Search Tree node
class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

// Insert a value into the BST
function insert(node, value) {
  if (node === null) return new TreeNode(value);

  if (value < node.value) {
    node.left = insert(node.left, value);
  } else if (value > node.value) {
    node.right = insert(node.right, value);
  }
  // Equal values are ignored (no duplicates)

  return node;
}

// Usage example
let root = null;
[8, 3, 10, 1, 6, 5].forEach((value) => {
  root = insert(root, value);
});

Done With the Learning

Mark BST Insertion as done and view it on your dashboard

Explore Other Tree Topics

BST Deletion

BST Searching

AVL Balancing

Binary Tree Types

Structure & Properties