BST Insert Operation in DSA Python - Time & Space Complexity

Time Complexity: BST Insert Operation

O(h)

Understanding Time Complexity

We want to understand how the time to insert a value in a Binary Search Tree (BST) changes as the tree grows.

How does the number of steps needed to insert depend on the size of the tree?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code inserts a value into a BST by moving down the tree until it finds the right spot.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls moving down one level of the tree.
• How many times: Once per level from root to the insertion point.

How Execution Grows With Input

Each insertion moves down the tree one step at a time until it finds the spot.

Input Size (n)	Approx. Operations (levels visited)
10	Up to 10
100	Up to 100
1000	Up to 1000

Pattern observation: In the worst case, the number of steps grows linearly with the number of nodes if the tree is unbalanced.

Final Time Complexity

Time Complexity: O(h) where h is the height of the tree.

This means the time depends on how tall the tree is, which can be as bad as the number of nodes if the tree is very unbalanced.

Common Mistake

[X] Wrong: "Insertion always takes the same time regardless of tree shape because it just compares values."

[OK] Correct: The number of comparisons depends on the tree height, which changes with how balanced the tree is. A tall, skinny tree takes longer to insert into than a balanced one.

Interview Connect

Understanding how tree shape affects insertion time helps you explain trade-offs and shows you know why balanced trees matter in real applications.

Self-Check

"What if we used a balanced BST like an AVL tree? How would the time complexity of insertion change?"

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