BST Inorder Predecessor in DSA Javascript - Time & Space Complexity

Time Complexity: BST Inorder Predecessor

O(h)

Understanding Time Complexity

We want to understand how long it takes to find the inorder predecessor in a Binary Search Tree (BST).

Specifically, how the time grows as the tree gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function inorderPredecessor(root, node) {
  if (node.left) {
    let pred = node.left;
    while (pred.right) {
      pred = pred.right;
    }
    return pred;
  }
  let pred = null;
  let curr = root;
  while (curr) {
    if (node.val > curr.val) {
      pred = curr;
      curr = curr.right;
    } else {
      curr = curr.left;
    }
  }
  return pred;
}
    

This code finds the inorder predecessor of a given node in a BST by checking left subtree or ancestors.

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, it moves down the height of the tree twice: once to find the rightmost node in left subtree, or once to find the ancestor.

How Execution Grows With Input

As the tree grows taller, the number of steps to find the predecessor grows roughly with the tree height.

Input Size (n)	Approx. Operations
10	Up to about 3-4 steps (tree height ~3-4)
100	Up to about 7 steps (tree height ~7)
1000	Up to about 10 steps (tree height ~10)

Pattern observation: The steps grow slowly as the tree height grows, not directly with total nodes.

Final Time Complexity

Time Complexity: O(h)

This means the time depends on the height of the tree, which is how deep it is from root to leaf.

Common Mistake

[X] Wrong: "Finding the inorder predecessor always takes time proportional to the number of nodes (n)."

[OK] Correct: We only move down the tree height, not all nodes, so time depends on height (h), not total nodes (n).

Interview Connect

Understanding this helps you explain how tree shape affects search times, a key skill for working with BSTs and similar structures.

Self-Check

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