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

func inorderPredecessor(root *Node, key int) *Node {
    var predecessor *Node
    current := root
    for current != nil {
        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 traversing the tree from the root.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Traversing down the tree nodes using a loop.
• How many times: At most once per level of the tree, moving to left or right child each step.

How Execution Grows With Input

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

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

Pattern observation: The number of steps grows with the tree height, which depends on how balanced the tree is.

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 time proportional to the total number of nodes in the tree."

[OK] Correct: The search only follows one path down the tree, so it depends on the height, not all 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 perfectly balanced? How would the time complexity change?"