Insertion in BST in Data Structures Theory - Step-by-Step Execution

Concept Flow - Insertion in BST

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?

↓

Repeat comparison

↓

Insert new node here

↓

Done

Start at the root and compare the new value with the current node. Move left if smaller, right if larger, until finding a null child where the new node is inserted.

Execution Sample

Data Structures Theory

Insert 15 into BST:
Start at root (20)
15 < 20? Go left (10)
15 > 10? Go right (null)
Insert 15 as right child of 10

This example inserts the value 15 into a BST by traversing from the root and placing it as the right child of 10.

Analysis Table

Step	Operation	Current Node	Comparison	Move To	Tree State
1	Start at root	20	15 < 20	Left child (10)	20 / 10 30
2	Compare with 10	10	15 > 10	Right child (null)	20 / 10 30
3	Insert new node	null	Insert 15	Insert here	20 / 10 30 \ 15
4	Done	-	-	-	Insertion complete

💡 Insertion stops when a null child is found and new node is inserted there.

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
current_node	20	10	null	null	null
new_value	15	15	15	15	15
tree_structure	20 / 10 30	20 / 10 30	20 / 10 30	20 / 10 30 \ 15	20 / 10 30 \ 15

Key Insights - 3 Insights

Why do we stop traversal when we find a null child?

Because a null child means there is no node there, so it's the correct place to insert the new node. This is shown in step 3 of the execution_table.

What happens if the new value is equal to a node's value?

Typically, BSTs do not allow duplicate values or handle them by a specific rule (like always going left or right). This example assumes no duplicates. The traversal compares strictly less or greater.

Why do we compare the new value with the current node at each step?

To decide whether to go left (if smaller) or right (if larger), ensuring the BST property is maintained. This decision is shown in steps 1 and 2.

Visual Quiz - 3 Questions

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

A 20

B 10

C null

D 15

💡 Hint

Check the 'Current Node' column in row for step 2.

At which step is the new node inserted into the tree?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look for the row where 'Insert new node' operation happens.

If the new value was 25 instead of 15, which child of 20 would we move to first?

A Left child

B Right child

C Insert at root

D No move, insert at root

💡 Hint

Refer to the comparison logic in the concept_flow and execution_table step 1.

Concept Snapshot

Insertion in BST:
- 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 position.
- Maintains BST property (left < node < right).

Full Transcript

Insertion in a Binary Search Tree (BST) starts at the root node. We compare the new value with the current node's value. If the new value is smaller, we move to the left child; if larger, to the right child. We repeat this process until we find a null child, which means there is no node there. At this null position, we insert the new node. This process maintains the BST property where left children are smaller and right children are larger than their parent nodes. For example, inserting 15 into a BST with root 20 and left child 10 involves moving left from 20 to 10, then moving right from 10 where the right child is null, and inserting 15 there. The traversal stops when the insertion point is found.

Practice

1. What happens when you insert a new value smaller than the current node in a Binary Search Tree (BST)?

easy

A. The new value replaces the current node.

B. The new value is inserted in the right subtree of the current node.

C. The new value is inserted in the left subtree of the current node.

D. The new value is ignored.

Solution

1. Step 1: Understand BST insertion rule for smaller values

   In a BST, if the new value is smaller than the current node, it must go to the left subtree.

2. Step 2: Apply the rule to the insertion process

   The new value is inserted into the left subtree, maintaining BST order.

3. Final Answer:

   The new value is inserted in the left subtree of the current node. -> Option C

4. Quick Check:

   Smaller value goes left [OK]

Hint: Smaller values always go to the left subtree [OK]

Common Mistakes:

• Inserting smaller values to the right subtree
• Replacing the current node instead of inserting
• Ignoring the new value

2. Which of the following is the correct way to insert a value into an empty Binary Search Tree (BST)?

easy

A. Set the new value as the root node of the BST.

B. Insert the new value as the left child of a random node.

C. Ignore the new value since the tree is empty.

D. Insert the new value as the right child of a random node.

Solution

1. Step 1: Identify insertion behavior for an empty BST

   When the BST is empty, the first inserted value becomes the root node.

2. Step 2: Confirm the correct insertion method

   Setting the new value as the root node initializes the BST correctly.

3. Final Answer:

   Set the new value as the root node of the BST. -> Option A

4. Quick Check:

   Empty tree insertion sets root [OK]

Hint: First insertion always becomes the root node [OK]

Common Mistakes:

• Trying to insert as child without a root
• Ignoring insertion in empty tree
• Inserting randomly without root

3. Consider the BST below:

    10
   /  
  5   15

What will the BST look like after inserting the value 12?

medium

A. 10
/
5 15
/
12

B. 10
/
5 12

15

C. 10
/
5 15

12

D. 10
/
5 12
/
15

Solution

1. Step 1: Compare 12 with root and right child

   12 is greater than 10, so move to right subtree. 12 is less than 15, so it goes to the left of 15.

2. Step 2: Insert 12 as left child of 15

   Place 12 as the left child of node 15 to maintain BST order.

3. Final Answer:

   12 is inserted as left child of 15. -> Option A

4. Quick Check:

   12 > 10 and 12 < 15, so left of 15 [OK]

Hint: Compare stepwise: left if smaller, right if larger [OK]

Common Mistakes:

• Inserting 12 as right child of 15
• Inserting 12 as right child of 10
• Ignoring BST order rules

4. Identify the error in the following BST insertion pseudocode:

function insert(node, value):
  if node is null:
    return new Node(value)
  if value > node.value:
    node.left = insert(node.left, value)
  else:
    node.right = insert(node.right, value)
  return node

medium

A. The code inserts smaller values to the left subtree instead of right.

B. The code does not handle the base case for empty tree.

C. The code incorrectly returns null instead of the node.

D. The code inserts larger values to the left subtree instead of right.

Solution

1. Step 1: Analyze insertion direction for larger values

   The code inserts values greater than current node into the left subtree, which is incorrect.

2. Step 2: Correct insertion direction for BST

   Larger values should be inserted into the right subtree to maintain BST order.

3. Final Answer:

   The code inserts larger values to the left subtree instead of right. -> Option D

4. Quick Check:

   Larger values go right, not left [OK]

Hint: Larger values always go right subtree [OK]

Common Mistakes:

• Swapping left and right insertion conditions
• Missing base case for null node
• Returning wrong node after insertion

5. You have a BST with values 20, 10, 30, 25, and 40 inserted in that order. Now you want to insert 30 again. Where should the new 30 be inserted according to standard BST insertion rules?

hard

A. As the left child of the existing 30 node.

B. As the right child of the existing 30 node.

C. Replace the existing 30 node with the new 30.

D. Do not insert duplicates in BST.

Solution

1. Step 1: Understand BST insertion for equal values

   Standard BST insertion places values equal to the current node in the right subtree.

2. Step 2: Insert new 30 as right child of existing 30

   The new 30 should be inserted as the right child of the existing 30 node.

3. Final Answer:

   As the right child of the existing 30 node. -> Option B

4. Quick Check:

   Equal values go right subtree [OK]

Hint: Equal values go to right subtree in BST [OK]

Common Mistakes:

• Inserting duplicates to the left subtree
• Replacing existing nodes instead of inserting
• Ignoring duplicates insertion rules