BST Inorder Predecessor in DSA Typescript - 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).

The question is: how does the time grow as the tree gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function inorderPredecessor(root: TreeNode | null, key: number): TreeNode | null {
  let predecessor: TreeNode | null = null;
  let current = root;
  while (current) {
    if (key <= current.val) {
      current = current.left;
    } else {
      predecessor = current;
      current = current.right;
    }
  }
  return predecessor;
}
    

This code finds the inorder predecessor of a given key in a BST by walking down the tree.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that moves down the tree nodes.
• How many times: At most once per level of the tree, until it reaches a leaf or finds the predecessor.

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	About 3 to 4 steps (tree height)
100	About 6 to 7 steps
1000	About 9 to 10 steps

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 the number of levels from root to leaf.

Common Mistake

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

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

Interview Connect

Understanding how tree height affects search time helps you explain and optimize tree operations clearly in interviews.

Self-Check

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