BST Insert Operation in DSA Typescript - Time & Space Complexity

Time Complexity: BST Insert Operation

O(h)

Understanding Time Complexity

We want to understand how the time to insert a new 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 and shape of the tree?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function insert(root: TreeNode | null, val: number): TreeNode {
  if (root === null) return new TreeNode(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: At most once per level from root to leaf, depending on tree height.

How Execution Grows With Input

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

Input Size (n)	Approx. Operations (steps down tree)
10	Up to 10 steps if tree is skewed, about 3-4 if balanced
100	Up to 100 steps if skewed, about 6-7 if balanced
1000	Up to 1000 steps if skewed, about 9-10 if balanced

Pattern observation: In worst case, steps grow linearly with n; in average case, steps grow slowly with tree height (log n).

Final Time Complexity

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

This means the time depends on how tall the tree is, which can be as small as log n or as large as n.

Common Mistake

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

[OK] Correct: If the tree is very unbalanced (like a linked list), insertion takes longer because you must go through many nodes.

Interview Connect

Understanding how tree shape affects insertion time helps you explain trade-offs and choose the right data structure in real problems.

Self-Check

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