BST Insert Operation in DSA Python

Mental Model

A binary search tree keeps values in order by placing smaller ones to the left and larger ones to the right. Inserting means finding the right empty spot following this rule.

Analogy: Imagine a sorted family tree where each person has two children spots: left for younger siblings and right for older siblings. To add a new sibling, you walk down the tree comparing ages until you find an empty spot.

    5
   / \
  3   7
 / \   \
2   4   8
↑ root

Dry Run Walkthrough

Input: Insert value 6 into BST: 5 -> 3 -> 7 -> 2 -> 4 -> 8

Goal: Add 6 in the correct position to keep BST order

Step 1: Start at root node 5

5 [curr↑]
/ \
3   7
/ \   \
2 4   8

Why: We begin comparing from the root to find where to insert

Step 2: 6 > 5, move curr to right child 7

5
/ \
3   7 [curr↑]
/ \   \
2 4   8

Why: Since 6 is bigger than 5, it belongs in the right subtree

Step 3: 6 < 7, move curr to left child which is null

5
/ \
3   7
/ \  / 
2 4 null [curr↑]
       8

Why: 6 is less than 7, so it should go to the left of 7

Step 4: Insert 6 as left child of 7

5
/ \
3   7
/ \  / \
2 4 6  8

Why: Found empty spot, place 6 here to keep BST order

Result:

5 -> 3 -> 7 -> 2 -> 4 -> 6 -> 8

Annotated Code

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)  # create new node if spot is empty
    if val < root.val:
        root.left = insert(root.left, val)  # go left if val smaller
    else:
        root.right = insert(root.right, val)  # go right if val bigger or equal
    return root

def print_bst(root):
    if root is None:
        return ""
    left = print_bst(root.left)
    right = print_bst(root.right)
    return (left + f"{root.val} -> " + right)

# Driver code
root = Node(5)
insert(root, 3)
insert(root, 7)
insert(root, 2)
insert(root, 4)
insert(root, 8)
insert(root, 6)

print(print_bst(root) + "null")

if root is None:

create new node when empty spot found

if val < root.val:

decide to go left subtree if value smaller

root.left = insert(root.left, val)

recursively insert in left subtree

else:

go right subtree if value bigger or equal

root.right = insert(root.right, val)

recursively insert in right subtree

return root

return current root to link back after insertion

Output

2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> null

Complexity Analysis

Time: O(h) where h is tree height because we follow one path down to insert

Space: O(h) due to recursion stack for the path from root to insertion point

vs Alternative: Compared to array insertion which can be O(n) due to shifting, BST insert is faster if tree is balanced

Edge Cases

Empty tree (root is None)

Creates a new node as root

DSA Python

if root is None:

Insert duplicate value

Duplicates go to right subtree by design

DSA Python

else:

Insert smallest or largest value

Inserted at leftmost or rightmost leaf respectively

DSA Python

if val < root.val:

When to Use This Pattern

When you need to keep data sorted with fast insertions and lookups, use BST insert pattern because it places values by comparing and branching left or right.

Common Mistakes

Mistake: Not returning the new node after insertion causing lost links
Fix: Always return the root after recursive insert to link nodes properly

Mistake: Inserting duplicates on left subtree breaking BST property
Fix: Insert duplicates consistently on right subtree or handle explicitly

Summary

Inserts a value into the binary search tree maintaining order.

Use when you want to add elements to a BST while keeping it sorted.

The key is to compare and move left or right until finding an empty spot.

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