BST Insert Operation in DSA Javascript

Mental Model

A binary search tree keeps smaller values on the left and bigger on the right. Inserting means finding the right empty spot following this rule.

Analogy: Imagine placing books on a shelf where smaller titles go to the left side and bigger titles to the right. To add a new book, you walk left or right until you find an empty spot.

    10
   /  \
  5    15
 / \   / \
null null null null

Dry Run Walkthrough

Input: Insert value 12 into BST: 10 -> 5 -> 15

Goal: Add 12 to the tree keeping the BST order

Step 1: Start at root node 10

10 [curr]
 /  \
5    15

Why: We begin comparing from the root to find the correct place

Step 2: Since 12 > 10, move curr to right child 15

10
 /  \
5    15 [curr]

Why: 12 is bigger than 10, so it must be in the right subtree

Step 3: Since 12 < 15, move curr to left child which is null

10
 /  \
5    15
     /
   null [curr]

Why: 12 is smaller than 15, so it should go to the left of 15

Step 4: Insert 12 as left child of 15

10
 /  \
5    15
     /
   12

Why: Found empty spot, insert new node here

Result:

10 -> 5 -> null
10 -> 15 -> 12 -> null

Annotated Code

DSA Javascript

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

class BST {
  constructor() {
    this.root = null;
  }

  insert(value) {
    const newNode = new Node(value);
    if (this.root === null) {
      this.root = newNode;
      return;
    }
    let curr = this.root;
    while (true) {
      if (value < curr.value) {
        if (curr.left === null) {
          curr.left = newNode; // insert here
          return;
        }
        curr = curr.left; // go left
      } else {
        if (curr.right === null) {
          curr.right = newNode; // insert here
          return;
        }
        curr = curr.right; // go right
      }
    }
  }

  print(node = this.root) {
    if (node === null) return "null";
    const left = this.print(node.left);
    const right = this.print(node.right);
    return `${node.value} -> ${left} , ${right}`;
  }
}

// Driver code
const bst = new BST();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(12);
console.log(bst.print());

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

handle empty tree by setting root to new node

while (true) {

loop to find correct insertion point

if (value < curr.value) { if (curr.left === null) { curr.left = newNode; return; } curr = curr.left; }

go left if value smaller, insert if spot empty

else { if (curr.right === null) { curr.right = newNode; return; } curr = curr.right; }

go right if value bigger or equal, insert if spot empty

Output

10 -> 5 -> null , null , 15 -> 12 -> null , null , null

Complexity Analysis

Time: O(h) where h is tree height because we traverse from root to leaf once

Space: O(1) because insertion uses constant extra space

vs Alternative: Compared to array insertions which can be O(n), BST insert is faster if tree is balanced

Edge Cases

Empty tree

New node becomes root

DSA Javascript

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

Insert duplicate value

Duplicates go to right subtree by design

DSA Javascript

else { ... curr = curr.right; }

Insert smallest or largest value

Inserted as leftmost or rightmost leaf

DSA Javascript

if (curr.left === null) or if (curr.right === null)

When to Use This Pattern

When you need to add values to a sorted tree structure while keeping order, use BST insert to place nodes correctly by comparing values.

Common Mistakes

Mistake: Not updating current pointer after moving left or right
Fix: Always assign curr = curr.left or curr = curr.right after moving

Mistake: Inserting node without checking if child is null
Fix: Check if left or right child is null before inserting

Summary

Inserts a new value into the binary search tree maintaining order.

Use when you want to add elements to a BST while keeping it sorted.

The key is to follow left or right pointers until you find an empty spot to insert.