BST Inorder Successor in DSA Typescript - Time & Space Complexity

Time Complexity: BST Inorder Successor

O(h)

Understanding Time Complexity

We want to understand how long it takes to find the next bigger value in a Binary Search Tree (BST).

How does the time needed grow as the tree gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code finds the next bigger node after a given node p 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 successor.

How Execution Grows With Input

Each step moves one level down the tree, so the number of steps depends on the tree height.

Input Size (n)	Approx. Operations
10	Up to 4 steps (if tree is balanced)
100	Up to 7 steps
1000	Up to 10 steps

Pattern observation: The steps grow slowly as the tree grows, roughly with the tree height.

Final Time Complexity

Time Complexity: O(h)

This means the time grows with the height of the tree, which is the number of levels from root to leaf.

Common Mistake

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

[OK] Correct: The search only moves down one path, not the whole tree, so it depends on tree height, not total 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 not balanced but skewed like a linked list? How would the time complexity change?"