Insertion in BST in Data Structures Theory - Time & Space Complexity

Time Complexity: Insertion in BST

O(h)

Understanding Time Complexity

When inserting a new value into a Binary Search Tree (BST), the time it takes depends on how deep we must go to find the right spot.

We want to understand how the number of steps grows as the tree gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function insert(node, value) {
  if (node == null) {
    return new Node(value);
  }
  if (value < node.value) {
    node.left = insert(node.left, value);
  } else {
    node.right = insert(node.right, value);
  }
  return node;
}
    

This code inserts a value into the BST by moving down the tree until it finds an empty 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: At most once per tree level, until a null spot is found.

How Execution Grows With Input

Each insertion moves down the tree levels. The number of steps depends on the tree height.

Input Size (n)	Approx. Operations (steps down tree)
10	Up to 4 steps
100	Up to 7 steps
1000	Up to 10 steps

Pattern observation: In a balanced tree, steps grow slowly with input size, roughly proportional to the tree height.

Final Time Complexity

Time Complexity: O(h)

This means the time to insert depends on the tree height, which is the number of levels from root to leaf.

Common Mistake

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

[OK] Correct: If the tree is unbalanced and looks like a list, insertion can take much longer because you must go through many nodes.

Interview Connect

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

Self-Check

"What if the BST is always perfectly balanced? How would the insertion time complexity change?"