BST Inorder Successor in DSA Javascript - Time & Space Complexity

Time Complexity: BST Inorder Successor

O(h)

Understanding Time Complexity

We want to understand how the time needed to find the inorder successor in a Binary Search Tree changes as the tree grows.

How does the number of steps grow when the tree has more nodes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function inorderSuccessor(root, p) {
  if (p.right) {
    let curr = p.right;
    while (curr.left) curr = curr.left;
    return curr;
  }
  let successor = null;
  let curr = root;
  while (curr) {
    if (p.val < curr.val) {
      successor = curr;
      curr = curr.left;
    } else {
      curr = curr.right;
    }
  }
  return successor;
}
    

This code finds the next bigger node (inorder successor) of a given node in a BST.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Traversing down the tree nodes using while loops.
• How many times: At most, the number of steps equals the height of the tree.

How Execution Grows With Input

As the tree grows, the height usually grows too, so the steps increase roughly with the height.

Input Size (n)	Approx. Operations (height)
10	About 3 to 4 steps
100	About 6 to 7 steps
1000	About 9 to 10 steps

Pattern observation: The number of steps grows slowly, roughly proportional to the tree height, which is often much smaller than total nodes.

Final Time Complexity

Time Complexity: O(h)

This means the time depends on the height of the tree, not the total number of nodes.

Common Mistake

[X] Wrong: "Finding the inorder successor always takes time proportional to the total number of nodes."

[OK] Correct: The search only follows a path down the tree, so it depends on the height, not all nodes.

Interview Connect

Understanding this helps you explain how tree shape affects search speed, a key skill for working with trees in real problems.

Self-Check

"What if the BST is balanced versus completely unbalanced? How would the time complexity change?"