BST Insert Operation in DSA Python - Execution Trace

Concept Flow - BST Insert Operation

Start at root

↓

Compare new value with current node

↓

New < current

↓

Go left

↓

Is left child None?

Yes↓

Insert new node here

↓

Done

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

Execution Sample

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

# Insert 25 into BST

Insert value 25 into the BST by traversing from root and placing it at the correct position.

Execution Table

Step	Operation	Current Node	Comparison	Pointer Changes	Visual State
1	Start at root	30	25 < 30	current moves to left child	┌────────┐ ┌────────┐ ┌────────┐ │ val:30 │──→ │ val:20 │ │ val:40 │ │ left:─┼──→ │ left:∅ │ │ right:∅│ │ right:└─∅ │ right:∅ │ │ │ └────────┘ └────────┘ └────────┘ root current
2	Compare with current node	20	25 > 20	current moves to right child	┌────────┐ ┌────────┐ ┌────────┐ │ val:30 │──→ │ val:20 │──→ │ val:∅ │ │ left:─┼──→ │ left:∅ │ │ │ │ right:└─∅ │ right:∅ │ │ │ └────────┘ └────────┘ └────────┘ root current
3	Right child is None	None	Insert new node here	20.right = Node(25)	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ val:30 │──→ │ val:20 │──→ │ val:25 │ │ val:40 │ │ left:─┼──→ │ left:∅ │ │ left:∅ │ │ right:∅│ │ right:└─∅ │ right:──┼──→│ right:∅ │ │ │ └────────┘ └────────┘ └────────┘ └────────┘ root left child new node right child
4	Insertion complete	N/A	N/A	N/A	BST updated with new node 25 inserted as right child of 20

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

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
current	root (30)	20 (left child of 30)	None (right child of 20)	Node(25) inserted as 20.right	Node(25)
20.right	None	None	None	Node(25)	Node(25)

Key Moments - 3 Insights

Why do we move to the right child when 25 > 20?

Because in a BST, values greater than the current node go to the right subtree. See execution_table step 2 where current moves from 20 to its right child.

Why do we insert the new node when the child pointer is None?

Because a None child means there is no node there, so it's the correct place to insert the new node. See execution_table step 3 where right child of 20 is None, so we insert 25 there.

What happens if the BST is empty initially?

If the BST is empty, the new node becomes the root. This is the starting point before step 1 in the execution_table.

Visual Quiz - 3 Questions

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

A 30

B 20

C 25

D None

💡 Hint

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

At which step does the insertion of the new node happen?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look for the step where 'Pointer Changes' shows linking the new node.

If the new value was 15 instead of 25, which direction would the traversal go from node 20?

A Left

B Right

C Stay at 20

D Insert at 30

💡 Hint

Recall BST rule: smaller values go left. See concept_flow for direction decisions.

Concept Snapshot

BST Insert Operation:
- Start at root node
- Compare new value with current node
- Move left if new < current, right if new > current
- Repeat until a None child is found
- Insert new node at that position
- Maintains BST property

Full Transcript

To insert a value into a Binary Search Tree (BST), start at the root node. Compare the new value with the current node's value. If the new value is smaller, move to the left child; if larger, move to the right child. Continue this process until you find a child pointer that is None, meaning no node exists there. Insert the new node at this position. This process keeps the BST property intact, where left children are smaller and right children are larger than their parent nodes.

Practice

1. What is the main purpose of the insert operation in a Binary Search Tree (BST)?

easy

A. To balance the BST automatically

B. To add a new value while keeping the BST property intact

C. To find the maximum value in the BST

D. To delete a node from the BST

Solution

1. Step 1: Understand the BST property

   A BST keeps values in order: left child smaller, right child larger.

2. Step 2: Purpose of insert operation

   Insert adds a new value so the tree remains ordered by BST rules.

3. Final Answer:

   To add a new value while keeping the BST property intact -> Option B

4. Quick Check:

   Insert = Add value maintaining order [OK]

Hint: Insert means add value keeping order [OK]

Common Mistakes:

• Confusing insert with delete
• Thinking insert balances the tree automatically
• Believing insert finds max value

2. Which of the following is the correct Python function signature for inserting a value into a BST node?

easy

A. def insert(root, value):

B. def insert(value, root):

C. def insert(value):

D. def insert(root):

Solution

1. Step 1: Identify parameters needed for insertion

   We need the root node to start and the value to insert.

2. Step 2: Check function signature correctness

   Signature with root first, then value is common and clear: def insert(root, value):.

3. Final Answer:

   def insert(root, value): -> Option A

4. Quick Check:

   Insert(root, value) signature [OK]

Hint: Insert needs root node and value [OK]

Common Mistakes:

• Swapping parameter order
• Missing root parameter
• Using only one parameter

3. What will be the output of the BST after inserting 7 into the BST shown below?

Initial BST (inorder): 3 -> 5 -> 8 -> 10 -> null

Code snippet:

root = BSTNode(5)
root.left = BSTNode(3)
root.right = BSTNode(8)
root.right.right = BSTNode(10)
root = insert(root, 7)
print_inorder(root)

medium

A. 3 -> 5 -> 7 -> 8 -> 10 -> null

B. 3 -> 5 -> 8 -> 7 -> 10 -> null

C. 3 -> 5 -> 8 -> 10 -> 7 -> null

D. 3 -> 5 -> 7 -> 10 -> 8 -> null

Solution

1. Step 1: Locate correct position for 7 in BST

   7 is greater than 5, so go right to 8. 7 is less than 8, so insert as left child of 8.

2. Step 2: Perform inorder traversal after insertion

   Inorder visits left, root, right: 3, 5, 7, 8, 10.

3. Final Answer:

   3 -> 5 -> 7 -> 8 -> 10 -> null -> Option A

4. Quick Check:

   Inorder after insert 7 = 3,5,7,8,10 [OK]

Hint: Insert left if smaller, right if bigger [OK]

Common Mistakes:

• Inserting 7 as right child of 8
• Not updating tree links correctly
• Confusing inorder output order

4. Consider this buggy insert function for BST:

def insert(root, val):
    if root is None:
        return BSTNode(val)
    if val < root.val:
        insert(root.left, val)
    else:
        insert(root.right, val)
    return root

What is the main problem with this code?

medium

A. It uses wrong comparison operators

B. It does not return the new root node

C. It inserts duplicates incorrectly

D. It does not assign the recursive insert result to child nodes

Solution

1. Step 1: Check recursive calls and assignments

   The recursive calls to insert do not assign the returned node back to root.left or root.right.

2. Step 2: Understand why assignment is needed

   Without assignment, new nodes are created but not linked to the tree, so insertion fails.

3. Final Answer:

   It does not assign the recursive insert result to child nodes -> Option D

4. Quick Check:

   Assign recursive insert to children [OK]

Hint: Always assign recursive insert result to child [OK]

Common Mistakes:

• Ignoring return value of recursive insert
• Assuming insert auto-links nodes
• Confusing comparison operators

5. You have a BST with nodes: 15, 10, 20, 8, 12, 17, 25. You want to insert 19. After insertion, what is the inorder traversal of the BST?

hard

A. 8 -> 10 -> 12 -> 15 -> 19 -> 17 -> 20 -> 25 -> null

B. 8 -> 10 -> 12 -> 15 -> 17 -> 20 -> 19 -> 25 -> null

C. 8 -> 10 -> 12 -> 15 -> 17 -> 19 -> 20 -> 25 -> null

D. 8 -> 10 -> 12 -> 15 -> 17 -> 20 -> 25 -> 19 -> null

Solution

1. Step 1: Find correct position for 19 in BST

   Start at root 15: 19 > 15, go right to 20. 19 < 20, go left to 17. 19 > 17, insert as right child of 17.

2. Step 2: Perform inorder traversal after insertion

   Inorder visits nodes in ascending order: 8, 10, 12, 15, 17, 19, 20, 25.

3. Final Answer:

   8 -> 10 -> 12 -> 15 -> 17 -> 19 -> 20 -> 25 -> null -> Option C

4. Quick Check:

   Inorder after insert 19 = sorted nodes [OK]

Hint: Insert by comparing down tree, then inorder print [OK]

Common Mistakes:

• Inserting 19 as left child of 20 without checking 17
• Misordering nodes in inorder traversal
• Confusing left and right child positions