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

This helps us know how the search time grows as the tree gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

Node* inorderPredecessor(Node* root, Node* curr) {
    if (curr->left != nullptr) {
        curr = curr->left;
        while (curr->right != nullptr) {
            curr = curr->right;
        }
        return curr;
    }
    Node* predecessor = nullptr;
    while (root != nullptr) {
        if (curr->data > root->data) {
            predecessor = root;
            root = root->right;
        } else if (curr->data < root->data) {
            root = root->left;
        } else {
            break;
        }
    }
    return predecessor;
}
    

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 left subtree's rightmost node or once up the ancestors.

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

Pattern observation: The steps grow slowly, roughly proportional to the tree height, not the total nodes.

Final Time Complexity

Time Complexity: O(h)

This means the time to find the inorder predecessor grows with the height of the BST, not the total number of nodes.

Common Mistake

[X] Wrong: "Finding the inorder predecessor always takes O(n) time because we might check all nodes."

[OK] Correct: We only follow a path down the tree, never visiting all nodes. So the time depends on tree height, not total nodes.

Interview Connect

Understanding this helps you explain how tree structure affects search times, a key skill in many coding problems.

Self-Check

"What if the BST is balanced vs completely skewed? How would the time complexity change?"