BST Find Minimum Element in DSA C++ - Time & Space Complexity

Time Complexity: BST Find Minimum Element

O(h)

Understanding Time Complexity

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

How does the time needed change as the tree grows bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

Node* findMin(Node* root) {
  if (root == nullptr) return nullptr;
  while (root->left != nullptr) {
    root = root->left;
  }
  return root;
}
    

This code finds the minimum element by going 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 repeatedly.
• How many times: At most once per level down the left side of the tree.

How Execution Grows With Input

As the tree grows, the time depends on the height of the leftmost path.

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

Pattern observation: In a balanced tree, steps grow slowly with size (logarithmically). In a skewed tree, steps can grow linearly.

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 just how many nodes it has.

Common Mistake

[X] Wrong: "Finding minimum always takes the same time regardless of tree shape."

[OK] Correct: If the tree is very unbalanced (like a linked list), it takes longer because you must go through many nodes.

Interview Connect

Understanding how tree shape affects search time is a key skill for working with trees and helps you explain your code clearly in interviews.

Self-Check

"What if the tree was balanced using a self-balancing method? How would the time complexity change?"