BST Insert Operation in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of the BST after inserting 15?

Given the BST below, what is the printed state after inserting the value 15?

Initial BST (in-order): 10 -> 20 -> 30 -> null

DSA Java

class Node {
    int val;
    Node left, right;
    Node(int val) { this.val = val; }
}

class BST {
    Node root;
    void insert(int val) {
        root = insertRec(root, val);
    }
    Node insertRec(Node root, int val) {
        if (root == null) return new Node(val);
        if (val < root.val) root.left = insertRec(root.left, val);
        else root.right = insertRec(root.right, val);
        return root;
    }
    void inorder(Node root) {
        if (root != null) {
            inorder(root.left);
            System.out.print(root.val + " -> ");
            inorder(root.right);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        BST tree = new BST();
        tree.insert(20);
        tree.insert(10);
        tree.insert(30);
        tree.insert(15);
        tree.inorder(tree.root);
        System.out.print("null");
    }
}

A 10 -> 20 -> 15 -> 30 -> null

B 10 -> 15 -> 20 -> 30 -> null

C 15 -> 10 -> 20 -> 30 -> null

D 10 -> 20 -> 30 -> 15 -> null

💡 Hint

Remember that in-order traversal prints nodes in ascending order for BST.

In-order traversal of a BST prints values in sorted order. After inserting 15, the BST contains 10, 15, 20, 30. So the output is 10 -> 15 -> 20 -> 30 -> null.

❓ Predict Output

intermediate

What is the output after inserting 5 into the BST?

Given the BST with nodes 10, 20, 30, what is the printed state after inserting 5?

Initial BST (in-order): 10 -> 20 -> 30 -> null

DSA Java

class Node {
    int val;
    Node left, right;
    Node(int val) { this.val = val; }
}

class BST {
    Node root;
    void insert(int val) {
        root = insertRec(root, val);
    }
    Node insertRec(Node root, int val) {
        if (root == null) return new Node(val);
        if (val < root.val) root.left = insertRec(root.left, val);
        else root.right = insertRec(root.right, val);
        return root;
    }
    void inorder(Node root) {
        if (root != null) {
            inorder(root.left);
            System.out.print(root.val + " -> ");
            inorder(root.right);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        BST tree = new BST();
        tree.insert(20);
        tree.insert(10);
        tree.insert(30);
        tree.insert(5);
        tree.inorder(tree.root);
        System.out.print("null");
    }
}

A 5 -> 20 -> 10 -> 30 -> null

B 10 -> 5 -> 20 -> 30 -> null

C 20 -> 10 -> 5 -> 30 -> null

D 5 -> 10 -> 20 -> 30 -> null

💡 Hint

In-order traversal prints nodes in ascending order.

After inserting 5, the BST contains 5, 10, 20, 30. In-order traversal prints them sorted: 5 -> 10 -> 20 -> 30 -> null.

🔧 Debug

advanced

What error occurs when inserting duplicate values in this BST insert method?

Consider the insert method below. What happens if we insert a value already present in the BST?

DSA Java

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

A Duplicates are ignored and not inserted

B Duplicates cause a StackOverflowError due to infinite recursion

C Duplicates are inserted to the right subtree, no error occurs

D Duplicates cause a NullPointerException

💡 Hint

Look at the condition for deciding left or right subtree insertion.

The code inserts duplicates in the right subtree because val == root.val goes to else branch. No error occurs, duplicates are allowed on right.

❓ Predict Output

advanced

What is the output after inserting 25 into this BST?

Given the BST with nodes 20, 10, 30, 25, what is the printed state after inserting 25 again?

Initial BST (in-order): 10 -> 20 -> 25 -> 30 -> null

DSA Java

class Node {
    int val;
    Node left, right;
    Node(int val) { this.val = val; }
}

class BST {
    Node root;
    void insert(int val) {
        root = insertRec(root, val);
    }
    Node insertRec(Node root, int val) {
        if (root == null) return new Node(val);
        if (val < root.val) root.left = insertRec(root.left, val);
        else root.right = insertRec(root.right, val);
        return root;
    }
    void inorder(Node root) {
        if (root != null) {
            inorder(root.left);
            System.out.print(root.val + " -> ");
            inorder(root.right);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        BST tree = new BST();
        tree.insert(20);
        tree.insert(10);
        tree.insert(30);
        tree.insert(25);
        tree.insert(25);
        tree.inorder(tree.root);
        System.out.print("null");
    }
}

A 10 -> 20 -> 25 -> 25 -> 30 -> null

B 10 -> 20 -> 25 -> 30 -> null

C 10 -> 20 -> 30 -> 25 -> 25 -> null

D 10 -> 20 -> 30 -> null

💡 Hint

Duplicates are inserted to the right subtree.

Inserting 25 twice adds two nodes with value 25. In-order traversal prints duplicates in sorted order.

🧠 Conceptual

expert

How many nodes are in the BST after inserting these values: 50, 30, 70, 20, 40, 60, 80, 70?

You insert the values 50, 30, 70, 20, 40, 60, 80, and then 70 again into an empty BST using the insert method below. How many nodes does the BST contain after all insertions?

DSA Java

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

A 8

B 9

C 6

D 7

💡 Hint

Duplicates are inserted as new nodes in the right subtree.

All values including the duplicate 70 are inserted as nodes. So total nodes = 8.

Practice

1. What is the main purpose of the insert operation in a Binary Search Tree (BST)?

easy

A. To add a new node while maintaining BST properties

B. To delete a node from the BST

C. To find the maximum value in the BST

D. To balance the BST after insertion

Solution

1. Step 1: Understand BST insert operation

   The insert operation adds a new node to the BST without breaking the BST property where left child nodes are smaller and right child nodes are larger.

2. Step 2: Identify the purpose

   Insertion is specifically for adding new nodes, not deleting or balancing the tree.

3. Final Answer:

   To add a new node while maintaining BST properties -> Option A

4. Quick Check:

   Insert = Add node [OK]

Hint: Insert means add node keeping order [OK]

Common Mistakes:

• Confusing insert with delete operation
• Thinking insert balances the tree automatically
• Assuming insert finds max value

2. Which of the following is the correct Java method signature for inserting a value into a BST node?

easy

A. public void insert(int value)

B. public boolean insert(int value, Node root)

C. public int insert(Node root, int value)

D. public Node insert(Node root, int value)

Solution

1. Step 1: Analyze method parameters and return type

   Insertion usually requires the root node and the value to insert. It returns the updated root node after insertion.

2. Step 2: Match signature with common BST insert pattern

   The method returns a Node and takes Node root and int value as parameters, matching public Node insert(Node root, int value).

3. Final Answer:

   public Node insert(Node root, int value) -> Option D

4. Quick Check:

   Insert method returns Node with root and value [OK]

Hint: Insert method returns updated root node [OK]

Common Mistakes:

• Using void return type instead of Node
• Swapping parameter order incorrectly
• Returning int instead of Node

3. What will be the inorder traversal output after inserting 15 into the BST with nodes 10, 5, 20?

medium

A. [5, 15, 10, 20]

B. [10, 5, 15, 20]

C. [5, 10, 15, 20]

D. [20, 15, 10, 5]

Solution

1. Step 1: Insert 15 into BST

   Start at root 10: 15 > 10, go right to 20. 15 < 20, insert as left child of 20.

2. Step 2: Perform inorder traversal

   Inorder visits left, root, right: left subtree [5], root 10, left child of 20 is 15, then 20. Result: [5, 10, 15, 20]

3. Final Answer:

   [5, 10, 15, 20] -> Option C

4. Quick Check:

   Inorder after insert = sorted list [OK]

Hint: Inorder traversal of BST is sorted [OK]

Common Mistakes:

• Inserting 15 as right child of 10 incorrectly
• Confusing preorder with inorder traversal
• Ignoring BST property during insertion

4. Identify the error in this BST insert method snippet:

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

medium

A. Incorrect base case for null root

B. Missing return when recursively inserting left or right

C. Using assignment instead of comparison in if condition

D. Returning void instead of Node

Solution

1. Step 1: Check recursive calls

   Recursive calls to insert(root.left, val) and insert(root.right, val) do not assign the returned Node back to root.left or root.right.

2. Step 2: Identify fix

   Must assign: root.left = insert(root.left, val); and root.right = insert(root.right, val); to update tree links.

3. Final Answer:

   Missing return when recursively inserting left or right -> Option B

4. Quick Check:

   Assign recursive insert result to child [OK]

Hint: Assign recursive insert result to child node [OK]

Common Mistakes:

• Not assigning recursive insert result to left/right child
• Confusing base case logic
• Returning wrong type

5. Given a BST with nodes inserted in this order: 30, 20, 40, 10, 25, 35, 50, what will be the structure after inserting 22? Choose the correct inorder traversal output.

hard

A. [10, 20, 22, 25, 30, 35, 40, 50]

B. [10, 20, 25, 22, 30, 35, 40, 50]

C. [10, 22, 20, 25, 30, 35, 40, 50]

D. [10, 20, 25, 30, 22, 35, 40, 50]

Solution

1. Step 1: Insert 22 into BST

   Start at root 30: 22 < 30 go left to 20; 22 > 20 go right to 25; 22 < 25 insert as left child of 25.

2. Step 2: Perform inorder traversal

   Inorder visits nodes in sorted order: 10, 20, 22, 25, 30, 35, 40, 50.

3. Final Answer:

   [10, 20, 22, 25, 30, 35, 40, 50] -> Option A

4. Quick Check:

   Inorder traversal is sorted list including 22 [OK]

Hint: Insert by BST rules, inorder is sorted [OK]

Common Mistakes:

• Inserting 22 in wrong subtree
• Misordering nodes in traversal
• Confusing preorder with inorder