BST Insert Operation in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after inserting nodes in BST

What is the printed state of the BST after inserting the values 10, 5, 15, 3, 7 in that order? The BST is printed in-order (left -> root -> right).

DSA Python

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

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

def inorder(root):
    return inorder(root.left) + [root.val] + inorder(root.right) if root else []

root = None
for v in [10, 5, 15, 3, 7]:
    root = insert(root, v)
print(inorder(root))

A [3, 5, 7, 10, 15]

B [10, 5, 15, 3, 7]

C [15, 10, 7, 5, 3]

D [3, 7, 5, 10, 15]

💡 Hint

Remember that in-order traversal of a BST prints values in sorted order.

Inserting nodes 10, 5, 15, 3, 7 creates a BST where in-order traversal visits nodes in ascending order: 3, 5, 7, 10, 15.

❓ Predict Output

intermediate

Output after inserting duplicate value in BST

What is the in-order traversal output after inserting values 20, 10, 30, 20 into an empty BST? Assume duplicates go to the right subtree.

DSA Python

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

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

def inorder(root):
    return inorder(root.left) + [root.val] + inorder(root.right) if root else []

root = None
for v in [20, 10, 30, 20]:
    root = insert(root, v)
print(inorder(root))

A [10, 20, 20, 30]

B [10, 20, 30]

C [20, 10, 30, 20]

D [30, 20, 20, 10]

💡 Hint

Duplicates are inserted to the right subtree, so the second 20 appears after the first in in-order.

The second 20 is inserted to the right of the first 20, so in-order traversal lists both 20s in order: 10, 20, 20, 30.

🔧 Debug

advanced

Identify the error in BST insert function

What error will this BST insert function cause when inserting values 8, 3, 10, 1, 6?

DSA Python

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

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

root = None
for v in [8, 3, 10, 1, 6]:
    root = insert(root, v)

# Print in-order traversal

def inorder(root):
    return inorder(root.left) + [root.val] + inorder(root.right) if root else []

print(inorder(root))

A Output: [1, 3, 6, 8, 10]

B TypeError: unsupported operand type(s) for <=: 'NoneType' and 'int'

C AttributeError: 'NoneType' object has no attribute 'val'

D Output: [8]

💡 Hint

Check if recursive calls update the left or right child pointers.

The insert function does not assign the recursive insert result back to root.left or root.right, so the tree does not grow beyond the root node. The in-order traversal prints only [8].

❓ Predict Output

advanced

BST structure after complex insertions

After inserting values [50, 30, 70, 20, 40, 60, 80] into an empty BST, what is the pre-order traversal output (root -> left -> right)?

DSA Python

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

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

def preorder(root):
    return [root.val] + preorder(root.left) + preorder(root.right) if root else []

root = None
for v in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, v)
print(preorder(root))

A [50, 70, 60, 80, 30, 20, 40]

B [20, 30, 40, 50, 60, 70, 80]

C [50, 30, 20, 40, 70, 60, 80]

D [80, 70, 60, 50, 40, 30, 20]

💡 Hint

Pre-order traversal visits root first, then left subtree, then right subtree.

The BST structure after insertion has root 50, left subtree with 30, 20, 40 and right subtree with 70, 60, 80. Pre-order visits root, left subtree in pre-order, then right subtree in pre-order.

🧠 Conceptual

expert

Number of nodes after multiple insertions in BST

If you insert the values [15, 10, 20, 10, 25, 15, 5] into an empty BST where duplicates are inserted to the right subtree, how many nodes will the BST contain?

A 5

B 7

C 4

D 6

💡 Hint

Duplicates are inserted as new nodes to the right subtree, so they increase the node count.

All values including duplicates are inserted as separate nodes. The list has 7 values, so the BST will have 7 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