BST Insert Operation in DSA Java

Mental Model

A binary search tree keeps smaller values on the left and bigger values on the right. To insert, we find the right spot by comparing values and then add the new node there.

Analogy: Imagine a sorted family tree where each person has children smaller than them on the left and bigger on the right. To add a new family member, you walk down the tree comparing names until you find the empty spot to place them.

    5
   / \
  3   7
 / \   \
2   4   8
↑ root

Dry Run Walkthrough

Input: Insert value 6 into BST: 5 -> 3 -> 7 -> 2 -> 4 -> 8

Goal: Add 6 in the correct position to keep BST rules

Step 1: Compare 6 with root 5, move right because 6 > 5

5 -> [curr->7]
 / \    \
3   7   8
/ \       
2  4       

Why: We go right because 6 is bigger than 5

Step 2: Compare 6 with 7, move left because 6 < 7

5 -> 7
 / \  ↑curr
3   7
/ \  
2  4  

Why: We go left because 6 is smaller than 7

Step 3: Left child of 7 is empty, insert 6 here

5 -> 7
 / \  
3   7
/ \  /
2  4 6

Why: Found empty spot to insert 6 maintaining BST order

Result:

5 -> 3 -> 7 -> 2 -> 4 -> 6 -> 8 -> null

Annotated Code

DSA Java

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

public class BSTInsert {
    public static Node insert(Node root, int val) {
        if (root == null) {
            return new Node(val); // insert here if spot is empty
        }
        if (val < root.val) {
            root.left = insert(root.left, val); // go left
        } else if (val > root.val) {
            root.right = insert(root.right, val); // go right
        }
        return root; // return unchanged root
    }

    public static void printInOrder(Node root) {
        if (root == null) return;
        printInOrder(root.left);
        System.out.print(root.val + " -> ");
        printInOrder(root.right);
    }

    public static void main(String[] args) {
        Node root = new Node(5);
        root.left = new Node(3);
        root.right = new Node(7);
        root.left.left = new Node(2);
        root.left.right = new Node(4);
        root.right.right = new Node(8);

        root = insert(root, 6);

        printInOrder(root);
        System.out.print("null\n");
    }
}

if (root == null) { return new Node(val); // insert here if spot is empty }

Insert new node when we find empty spot

if (val < root.val) { root.left = insert(root.left, val); // go left }

Traverse left subtree if value is smaller

else if (val > root.val) { root.right = insert(root.right, val); // go right }

Traverse right subtree if value is bigger

return root; // return unchanged root

Return current node after insertion

Output

2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> null

Complexity Analysis

Time: O(h) where h is tree height because we follow one path down to insert

Space: O(h) due to recursion stack in worst case (skewed tree)

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

Edge Cases

Empty tree (root is null)

New node becomes root

DSA Java

if (root == null) {
    return new Node(val); // insert here if spot is empty
}

Insert duplicate value

No insertion happens, tree remains unchanged

DSA Java

else if (val > root.val) {
    root.right = insert(root.right, val); // go right
}

When to Use This Pattern

When you need to add a value to a sorted tree structure while keeping order, use BST insert to find the correct spot efficiently.

Common Mistakes

Mistake: Not returning the updated subtree after insertion causing lost links
Fix: Always assign the recursive call result back to root.left or root.right

Mistake: Inserting duplicates without handling causing infinite recursion
Fix: Add condition to ignore or handle duplicates explicitly

Summary

Inserts a new value into the binary search tree while keeping its order.

Use when you want to add elements to a BST efficiently.

The key is to compare and move left or right until you find an empty spot to insert.

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