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.