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.

Practice

1. What does the insert operation do in a Binary Search Tree (BST)?

easy

A. Searches for a node with a given value

B. Adds a new node in the correct position to maintain BST order

C. Deletes a node from the tree

D. Balances the tree automatically after insertion

Solution

1. Step 1: Understand BST property

   In a BST, left child nodes are smaller and right child nodes are larger than the parent node.

2. Step 2: Purpose of insert operation

   The insert operation places a new value in the tree so that this property remains true.

3. Final Answer:

   Adds a new node in the correct position to maintain BST order -> Option B

4. Quick Check:

   Insert means add node correctly [OK]

Hint: Insert means add node keeping BST order intact [OK]

Common Mistakes:

• Confusing insert with delete operation
• Thinking insert balances the tree automatically
• Assuming insert searches only without adding

2. Which of the following is the correct syntax to insert a value val into a BST node root in JavaScript?

easy

A. root = insert(root, val);

B. root.insert(val);

C. insert(root, val);

D. insert(val, root);

Solution

1. Step 1: Understand function usage in BST insert

   Insert usually returns the new root after insertion, so assignment is needed.

2. Step 2: Check parameter order and assignment

   The function takes the root and value, returns updated root, so root = insert(root, val); is correct.

3. Final Answer:

   root = insert(root, val); -> Option A

4. Quick Check:

   Assign updated root after insert [OK]

Hint: Insert returns new root, so assign it back [OK]

Common Mistakes:

• Calling insert without assignment
• Passing parameters in wrong order
• Using method call on root without method defined

3. What will be the inorder traversal output after inserting 5 into this BST?

    10
   /  
  3    15
   
    4

Insert 5 and then print inorder traversal.

medium

A. [3, 5, 4, 10, 15]

B. [3, 4, 10, 5, 15]

C. [3, 4, 5, 10, 15]

D. [5, 3, 4, 10, 15]

Solution

1. Step 1: Insert 5 into BST

   Start at root 10, 5 < 10 go left to 3, 5 > 3 go right to 4, 5 > 4 insert as right child of 4.

2. Step 2: Perform inorder traversal

   Inorder visits left, root, right: nodes visited in order: 3, 4, 5, 10, 15.

3. Final Answer:

   [3, 4, 5, 10, 15] -> Option C

4. Quick Check:

   Inorder sorted after insert [OK]

Hint: Inorder traversal of BST is sorted list [OK]

Common Mistakes:

• Inserting 5 as left child of 4
• Mixing preorder or postorder traversal output
• Ignoring BST property during insertion

4. Given this insert function snippet, what is the error?

function insert(root, val) {
  if (root == null) {
    return new Node(val);
  }
  if (val < root.val) {
    insert(root.left, val);
  } else {
    insert(root.right, val);
  }
  return root;
}

medium

A. Returning root before insertion

B. Incorrect base case condition

C. Using '==' instead of '===' for null check

D. Missing assignment of recursive insert result to root.left or root.right

Solution

1. Step 1: Check recursive calls

   Recursive calls to insert do not assign the returned node back to root.left or root.right, so tree structure won't update.

2. Step 2: Correct recursive assignment

   Should assign: root.left = insert(root.left, val); or root.right = insert(root.right, val); to update links.

3. Final Answer:

   Missing assignment of recursive insert result to root.left or root.right -> Option D

4. Quick Check:

   Assign recursive insert result to child [OK]

Hint: Always assign recursive insert result to child pointer [OK]

Common Mistakes:

• Ignoring assignment in recursion
• Confusing base case with recursive step
• Thinking '==' causes error here

5. You have a BST with nodes 20, 10, 30. You insert 25, then 5, then 35. What is the preorder traversal of the BST after all insertions?

hard

A. [20, 10, 5, 30, 25, 35]

B. [20, 30, 25, 35, 10, 5]

C. [10, 5, 20, 30, 25, 35]

D. [20, 10, 30, 5, 25, 35]

Solution

1. Step 1: Insert nodes step-by-step

   Start with root 20, left 10, right 30.
   Insert 25: 25 < 30 and > 20, goes left of 30.
   Insert 5: less than 10, goes left of 10.
   Insert 35: greater than 30, goes right of 30.

2. Step 2: Preorder traversal

   Preorder visits root, left subtree, right subtree.
   Visit 20, then left subtree (10, 5), then right subtree (30, 25, 35).
   So preorder: [20, 10, 5, 30, 25, 35]

3. Final Answer:

   [20, 10, 5, 30, 25, 35] -> Option A

4. Quick Check:

   Preorder = root-left-right [OK]

Hint: Preorder = root, left subtree, right subtree [OK]

Common Mistakes:

• Mixing preorder with inorder or postorder
• Inserting nodes in wrong position
• Forgetting to update tree after insert