BST Find Minimum Element in DSA Javascript - Time & Space Complexity

Time Complexity: BST Find Minimum Element

O(h)

Understanding Time Complexity

We want to know how long it takes to find the smallest value in a Binary Search Tree (BST).

How does the time grow as the tree gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function findMin(root) {
  let current = root;
  while (current.left !== null) {
    current = current.left;
  }
  return current.value;
}
    

This code finds the smallest value by going left until no more left child exists.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Moving down the left child nodes in the tree.
• How many times: At most once per level of the tree, until the leftmost node is reached.

How Execution Grows With Input

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

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

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

Final Time Complexity

Time Complexity: O(h)

This means the time depends on the height of the tree, going down one level at a time.

Common Mistake

[X] Wrong: "Finding the minimum always takes O(1) time because it's just one step."

[OK] Correct: The minimum is found by moving down the left side, which can take many steps if the tree is tall.

Interview Connect

Understanding how tree height affects search time helps you explain why balanced trees are faster and shows your grasp of data structure efficiency.

Self-Check

"What if the BST is perfectly balanced? How would the time complexity change?"