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?"