BST Insert Operation in DSA Java - Execution Trace

Concept Flow - BST Insert Operation

Start at root

↓

Compare new value with current node

↓

Is new value < current node?

Yes→Go to left child

↓

Is left child null?

↓

Go to right child

↓

Is right child null?

No +---> Back to Compare↓

Insert new node here

↓

Done

↩No +---> Back to Compare

Start at the root and compare the new value with current node. Move left if smaller, right if larger. Insert when a null child is found.

Execution Sample

DSA Java

class Node {
  int data;
  Node left, right;
}

Node insert(Node root, int val) {
  if (root == null) {
    Node newNode = new Node();
    newNode.data = val;
    newNode.left = null;
    newNode.right = null;
    return newNode;
  }
  Node parent = null;
  Node current = root;
  while (current != null) {
    parent = current;
    if (val < current.data) {
      current = current.left;
    } else {
      current = current.right;
    }
  }
  Node newNode = new Node();
  newNode.data = val;
  newNode.left = null;
  newNode.right = null;
  if (val < parent.data) {
    parent.left = newNode;
  } else {
    parent.right = newNode;
  }
  return root;
}

Inserts a value into the BST by traversing from root and placing it at the correct leaf position.

Execution Table

Step	Operation	Current Node	Pointer Changes	Visual State
1	Start at root	50	root points to 50	┌────────┐ │ data:50│ │ left:──┼──→ ∅ │ right:─┼──→ ∅ └────────┘ root
2	Compare 30 with 50	50	No pointer change	Same as step 1
3	30 < 50, go left	50	current moves to left child (null)	┌────────┐ ∅ │ data:50│ │ left:──┼──→ ∅ │ right:─┼──→ ∅ └────────┘ root
4	Left child null, insert 30	50	left child of 50 points to new node 30	┌────────┐ ┌────────┐ │ data:50│ │ data:30│ │ left:──┼──→ │ left:∅ │ │ right:─┼──→ │ right:∅│ └────────┘ └────────┘ root left child
5	Done	50	Insertion complete	Final tree: ┌────────┐ ┌────────┐ │ data:50│ │ data:30│ │ left:──┼──→ │ left:∅ │ │ right:─┼──→ │ right:∅│ └────────┘ └────────┘ root left child

💡 Insertion done when a null child is found and new node is linked there.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
root	Node(50)	Node(50)	Node(50)	Node(50)	Node(50)
current	Node(50)	Node(50)	null (left child of 50)	Node(30) (new node)	Node(30)
newNode	null	null	null	Node(30)	Node(30)

Key Moments - 3 Insights

Why do we check if the left or right child is null before inserting?

Because insertion happens only at a leaf position where the child pointer is null, as shown in step 4 of the execution_table.

Why do we move current to left or right child instead of inserting immediately?

We must find the correct position to maintain BST order, so we traverse down until we find a null child, as seen in steps 2 and 3.

What happens if the tree is empty (root is null)?

Then the new node becomes the root directly, but this example assumes root is not null to show traversal.

Visual Quiz - 3 Questions

Look at the execution_table, what is the current node at step 3?

A Node with data 30

B Node with data 50

C Null (left child of 50)

D Root is null

💡 Hint

Check the 'Current Node' column at step 3 in the execution_table.

At which step is the new node with value 30 inserted?

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look for the step where pointer changes show linking new node 30.

If the new value was 70 instead of 30, which pointer would change?

A Right child of 50

B Left child of 50

C Root pointer

D No pointer changes

💡 Hint

Recall BST property: values greater than node go to right child.

Concept Snapshot

BST Insert Operation:
- Start at root node
- Compare new value with current node
- Move left if smaller, right if larger
- Repeat until null child found
- Insert new node at null child
- Maintains BST order property

Full Transcript

The BST insert operation starts at the root node. We compare the new value with the current node's data. If the new value is smaller, we move to the left child; if larger, to the right child. We continue this traversal until we find a null child pointer, which means the correct place to insert the new node. Then we link the new node there, maintaining the binary search tree property. This process is shown step-by-step in the execution table and pointer diagrams.

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