Time Complexity: BST Inorder Successor
O(h)
0
0
BST Inorder Successor in DSA Go - Time & Space Complexity
Understanding Time Complexity
We want to understand how long it takes to find the next bigger value in a Binary Search Tree (BST) after a given node.
How does the time needed grow as the tree gets bigger?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
// Find the inorder successor of a node in BST
func inorderSuccessor(root, p *TreeNode) *TreeNode {
var successor *TreeNode
current := root
for current != nil {
if p.Val < current.Val {
successor = current
current = current.Left
} else {
current = current.Right
}
}
return successor
}
This code finds the next larger node after p in a BST by walking down from the root.
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 tree level, moving left or right.
How Execution Grows With Input
As the tree grows taller, the number of steps to find the successor grows roughly with the height.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | Up to 4 steps (height ~4) |
| 100 | Up to 7 steps (height ~7) |
| 1000 | Up to 10 steps (height ~10) |
Pattern observation: The steps grow slowly as the tree height grows, not with total nodes.
Final Time Complexity
Time Complexity: O(h)
This means the time depends on the tree height, 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 (n)."
[OK] Correct: The search moves down one path only, not the whole tree, so it depends on height, not total nodes.
Interview Connect
Knowing how tree height affects search time helps you explain and optimize tree operations clearly in interviews.
Self-Check
"What if the BST is balanced vs completely unbalanced? How would the time complexity change?"