BST Insert Operation in DSA Go - Time & Space Complexity

Time Complexity: BST Insert Operation

O(h)

Understanding Time Complexity

We want to understand how the time to insert a value into a Binary Search Tree changes as the tree grows.

How does the number of steps needed to insert a new value change when the tree has more nodes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func Insert(root *Node, val int) *Node {
    if root == nil {
        return &Node{Val: 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 Binary Search Tree by moving left or right until it finds the right spot.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls moving down the tree nodes.
• How many times: At most once per tree level until the correct leaf spot is found.

How Execution Grows With Input

Each insert moves down one level in the tree. The number of levels depends on the tree height.

Input Size (n)	Approx. Operations (tree height)
10	About 3 to 10 steps depending on tree shape
100	About 7 to 100 steps depending on tree shape
1000	About 10 to 1000 steps depending on tree shape

Pattern observation: If the tree is balanced, steps grow slowly (logarithmic). If unbalanced, steps grow linearly with n.

Final Time Complexity

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

This means the time to insert depends on how tall the tree is, which can be small if balanced or large if skewed.

Common Mistake

[X] Wrong: "Insertion always takes the same time regardless of tree shape."

[OK] Correct: The tree shape affects height; a tall, skewed tree means more steps to insert.

Interview Connect

Understanding how tree height affects insertion helps you explain and improve tree operations in real problems.

Self-Check

"What if the tree is always perfectly balanced? How would that change the time complexity of insertion?"

Practice

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

easy

A. To balance the BST after insertion

B. To add a new node 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 BST property

   In a BST, left child nodes are smaller and right child nodes are larger than the parent node.

2. Step 2: Purpose of Insert

   Insert adds a new node in the correct position to keep this order intact.

3. Final Answer:

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

4. Quick Check:

   Insert = Add node correctly [OK]

Hint: Insert adds nodes preserving BST order [OK]

Common Mistakes:

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

2. Which of the following is the correct way to declare a BST node struct in Go for insertion?

easy

A. type Node struct { value int; left *Node; right *Node }

B. type Node struct { val int; left Node; right Node }

C. type Node struct { value int; left Node; right Node }

D. type Node struct { value int; left *Node; right Node }

Solution

1. Step 1: Understand pointer usage in Go structs

   BST nodes must use pointers for left and right to link nodes dynamically.

2. Step 2: Check each option

   type Node struct { value int; left *Node; right *Node } uses pointers (*Node) for left and right, correct for BST links.

3. Final Answer:

   type Node struct { value int; left *Node; right *Node } -> Option A

4. Quick Check:

   Use pointers for child nodes [OK]

Hint: Use *Node pointers for left and right children [OK]

Common Mistakes:

• Using value types instead of pointers for children
• Mixing pointer and non-pointer types incorrectly
• Incorrect field names like 'val' instead of 'value'

3. Given the following BST and insertion code snippet in Go, what will be the inorder traversal output after inserting 6?

root := &Node{value: 5}
root.left = &Node{value: 3}
root.right = &Node{value: 7}
Insert(root, 6)
// Inorder traversal function prints nodes in ascending order

medium

A. 3 5 6 7

B. 3 5 7 6

C. 5 3 6 7

D. 3 6 5 7

Solution

1. Step 1: Understand BST structure before insertion

   Initial tree: 5 root, 3 left child, 7 right child.

2. Step 2: Insert 6

   6 is less than 7 but greater than 5, so it becomes left child of 7.

3. Step 3: Inorder traversal

   Inorder visits left, root, right: 3, 5, 6, 7.

4. Final Answer:

   3 5 6 7 -> Option A

5. Quick Check:

   Inorder after insert = 3 5 6 7 [OK]

Hint: Insert left if smaller, right if larger; inorder sorts [OK]

Common Mistakes:

• Placing 6 as right child of 5 directly
• Confusing inorder traversal order
• Ignoring BST property during insertion

4. Identify the error in this Go function for inserting a value into a BST:

func Insert(root *Node, val int) *Node {
  if root == nil {
    return &Node{value: val}
  }
  if val < root.value {
    root.left = Insert(root.left, val)
  } else if val > root.value {
    root.right = Insert(root.right, val)
  }
  return root
}

medium

A. The function uses wrong comparison operators (< and >)

B. The function returns nil instead of root

C. The function does not handle duplicate values explicitly

D. The function does not create new nodes correctly

Solution

1. Step 1: Review function logic

   Function inserts recursively left or right based on value comparison.

2. Step 2: Check duplicate handling

   When val equals root.value, no insertion or special handling occurs.

3. Step 3: Identify error

   Duplicates are ignored silently; function should handle or document this case.

4. Final Answer:

   The function does not handle duplicate values explicitly -> Option C

5. Quick Check:

   Duplicates need explicit handling [OK]

Hint: Check if duplicates are handled in insert [OK]

Common Mistakes:

• Assuming duplicates insert automatically
• Returning nil instead of root
• Using wrong comparison signs

5. You have a BST with nodes 10, 5, 15, 3, 7, 12, 18. You want to insert 6. Which sequence of nodes will you visit during the insertion process?

hard

A. 10 -> 5 -> 7 -> 6

B. 10 -> 15 -> 12

C. 10 -> 5 -> 3

D. 10 -> 5 -> 7

Solution

1. Step 1: Start at root 10

   6 is less than 10, move to left child 5.

2. Step 2: Compare with 5

   6 is greater than 5, move to right child 7.

3. Step 3: Compare with 7

   6 is less than 7, insert as left child of 7.

4. Final Answer:

   10 -> 5 -> 7 -> Option D

5. Quick Check:

   Traverse nodes comparing values [OK]

Hint: Follow BST rules: left if smaller, right if larger [OK]

Common Mistakes:

• Visiting wrong child nodes
• Including inserted node in visited sequence
• Confusing greater and smaller comparisons