Time Complexity: BST Find Minimum Element
O(h)
0
0
BST Find Minimum Element in DSA Typescript - Time & Space Complexity
Understanding Time Complexity
Finding the smallest value in a Binary Search Tree (BST) helps us quickly access the minimum data. We want to understand how the time it takes grows as the tree gets bigger.
How does the search time change when the tree has more nodes?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
function findMin(root: TreeNode | null): number | null {
if (root === null) return null;
let current = root;
while (current.left !== null) {
current = current.left;
}
return current.val;
}
This code finds the minimum element by moving left until no more left child exists.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Moving from a node to its left child.
- How many times: At most once per level down the left side of the tree.
How Execution Grows With Input
Each step moves one level down the left side of the tree until the smallest node is found.
| Input Size (n) | Approx. Operations (steps down left) |
|---|---|
| 10 | Up to 4-5 steps (depends on tree shape) |
| 100 | Up to 6-7 steps |
| 1000 | Up to 9-10 steps |
Pattern observation: The number of steps grows with the height of the tree, not the total nodes.
Final Time Complexity
Time Complexity: O(h) where h is the tree height
This means the time depends on how tall the tree is, not how many nodes it has in total.
Common Mistake
[X] Wrong: "Finding the minimum always takes time proportional to the total number of nodes."
[OK] Correct: The search only follows the left children, so it depends on the tree height, which can be much smaller than total nodes.
Interview Connect
Understanding how tree height affects search time helps you explain why balanced trees are faster. This skill shows you can analyze and improve data structure performance.
Self-Check
What if the BST is perfectly balanced? How would the time complexity change?