BST Insert Operation in DSA Java - Time & Space Complexity

Time Complexity: BST Insert Operation

O(h)

Understanding Time Complexity

We want to understand how the time to insert a value in a Binary Search Tree (BST) changes as the tree grows.

How does the number of steps needed to insert depend on the tree size?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

    Node root;

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

This code inserts a value into a BST by recursively finding the correct spot.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls moving down the tree nodes.
• How many times: Once per level from root to leaf where insertion happens.

How Execution Grows With Input

Each insertion travels from the root down to a leaf position. The number of steps depends on the tree height.

Input Size (n)	Approx. Operations (steps down tree)
10	About 3 to 10 steps depending on tree shape
100	About 7 to 100 steps depending on tree shape
1000	About 10 to 1000 steps depending on tree shape

Pattern observation: In a balanced tree, steps grow slowly (logarithmic). In a skewed tree, steps grow linearly with n.

Final Time Complexity

Time Complexity: O(h) where h is the tree height

This means the time depends on how tall the tree is, which can be small if balanced or large if skewed.

Common Mistake

[X] Wrong: "Insertion always takes the same time regardless of tree shape."

[OK] Correct: The tree height changes with shape; a tall, unbalanced tree means more steps to insert.

Interview Connect

Understanding how tree shape affects insertion time helps you explain trade-offs and shows you know why balanced trees matter.

Self-Check

"What if we used a self-balancing BST like AVL or Red-Black Tree? How would the time complexity change?"

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