Time Complexity: BST Inorder Successor
O(h)
0
0
BST Inorder Successor in DSA C++ - 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 change as the tree grows larger?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
// Find inorder successor in BST
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
TreeNode* successor = nullptr;
while (root) {
if (p->val < root->val) {
successor = root;
root = root->left;
} else {
root = root->right;
}
}
return successor;
}
This code finds the next larger node after a given node 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 level of the tree, from root to leaf.
How Execution Grows With Input
As the tree grows taller, the number of steps to find the successor grows roughly with the height of the tree.
| 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 grows, roughly proportional to the tree height.
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 successor always takes O(n) time because we might check every node."
[OK] Correct: The search only follows one path down the tree, not all nodes, so it depends on the tree height, not total nodes.
Interview Connect
Understanding this helps you explain how tree structure affects search speed, a key skill for working with trees in real problems.
Self-Check
"What if the BST is balanced versus completely unbalanced? How would the time complexity change?"