BST Insert Operation in DSA Javascript - 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 a new value change when the tree has more nodes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function insertNode(root, value) {
  if (root === null) {
    return { val: value, left: null, right: null };
  }
  if (value < root.val) {
    root.left = insertNode(root.left, value);
  } else {
    root.right = insertNode(root.right, value);
  }
  return root;
}
    

This code inserts a new value into a BST 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
100	About 7 to 100 steps
1000	About 10 to 1000 steps

Pattern observation: If the tree is balanced, steps grow slowly (logarithmic). If unbalanced, steps can grow linearly with 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 small if balanced or large if skewed.

Common Mistake

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

[OK] Correct: The shape of the tree affects how many steps we take. A tall, unbalanced tree means more steps.

Interview Connect

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

Self-Check

What if we changed the BST to a balanced tree like an AVL or Red-Black tree? How would the time complexity change?