BST Insert Operation in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of the BST after these insertions?

Consider a Binary Search Tree (BST) initially empty. Insert the values 10, 5, 15, 3, 7 in this order. What is the in-order traversal output of the BST?

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) {
      this.root = newNode;
      return;
    }
    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) {
          current.left = newNode;
          return;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          return;
        }
        current = current.right;
      }
    }
  }

  inorder(node, result = []) {
    if (!node) return result;
    this.inorder(node.left, result);
    result.push(node.value);
    this.inorder(node.right, result);
    return result;
  }
}

const tree = new BST();
tree.insert(10);
tree.insert(5);
tree.insert(15);
tree.insert(3);
tree.insert(7);
console.log(tree.inorder(tree.root));

A [5, 3, 7, 10, 15]

B [10, 5, 15, 3, 7]

C [15, 10, 7, 5, 3]

D [3, 5, 7, 10, 15]

💡 Hint

In-order traversal of a BST returns values in sorted order.

Inserting values 10, 5, 15, 3, 7 creates a BST where in-order traversal visits nodes in ascending order: 3, 5, 7, 10, 15.

❓ Predict Output

intermediate

What is the BST structure after inserting 8 into this tree?

Given a BST with nodes 10 (root), 5 (left child), and 15 (right child), what is the in-order traversal after inserting 8?

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) {
      this.root = newNode;
      return;
    }
    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) {
          current.left = newNode;
          return;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          return;
        }
        current = current.right;
      }
    }
  }

  inorder(node, result = []) {
    if (!node) return result;
    this.inorder(node.left, result);
    result.push(node.value);
    this.inorder(node.right, result);
    return result;
  }
}

const tree = new BST();
tree.root = new Node(10);
tree.root.left = new Node(5);
tree.root.right = new Node(15);
tree.insert(8);
console.log(tree.inorder(tree.root));

A [5, 8, 10, 15]

B [5, 8, 10, 15, 8]

C [5, 10, 8, 15]

D [8, 5, 10, 15]

💡 Hint

Insert 8 as right child of 5 because 8 > 5 and 8 < 10.

8 is inserted as the right child of 5. In-order traversal visits nodes in ascending order: 5, 8, 10, 15.

🔧 Debug

advanced

Why does this BST insert code cause an infinite loop?

Look at this insert method for BST. Why does it cause an infinite loop when inserting a value equal to a node's value?

DSA Javascript

insert(value) {
  const newNode = new Node(value);
  if (!this.root) {
    this.root = newNode;
    return;
  }
  let current = this.root;
  while (true) {
    if (value < current.value) {
      if (!current.left) {
        current.left = newNode;
        return;
      }
      current = current.left;
    } else if (value > current.value) {
      if (!current.right) {
        current.right = newNode;
        return;
      }
      current = current.right;
    }
  }
}

A The root node is not updated when inserting duplicate values.

B The newNode is never created inside the loop, causing infinite loop.

C The code does not handle the case when value equals current.value, causing an infinite loop.

D The while loop condition is always true without any break statement.

💡 Hint

Check what happens when value equals current.value.

When value equals current.value, neither if nor else if conditions are true, so current never changes and loop runs forever.

❓ Predict Output

advanced

What is the output after inserting duplicate values in BST?

Given a BST where duplicates are inserted to the right subtree, what is the in-order traversal after inserting 10, 5, 15, 10, 5?

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) {
      this.root = newNode;
      return;
    }
    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) {
          current.left = newNode;
          return;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          return;
        }
        current = current.right;
      }
    }
  }

  inorder(node, result = []) {
    if (!node) return result;
    this.inorder(node.left, result);
    result.push(node.value);
    this.inorder(node.right, result);
    return result;
  }
}

const tree = new BST();
tree.insert(10);
tree.insert(5);
tree.insert(15);
tree.insert(10);
tree.insert(5);
console.log(tree.inorder(tree.root));

A [5, 5, 10, 10, 15]

B [5, 10, 5, 10, 15]

C [10, 5, 15, 10, 5]

D [5, 10, 15]

💡 Hint

Duplicates go to the right subtree in this BST.

Duplicates 10 and 5 are inserted as right children of existing nodes with same values, so in-order traversal shows duplicates in sorted order.

🧠 Conceptual

expert

What is the time complexity of inserting N sorted values into an empty BST?

If you insert N values sorted in ascending order into an empty BST, what is the time complexity of all insertions combined?

A O(N)

B O(N^2)

C O(log N)

D O(N log N)

💡 Hint

Think about how the tree shape changes when inserting sorted values.

Inserting sorted values creates a skewed tree (like a linked list), so each insertion takes O(N) in worst case, total O(N^2).

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