BST Find Minimum Element in DSA Go - 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.

func findMin(root *Node) *Node {
    current := root
    for current.Left != nil {
        current = current.Left
    }
    return current
}
    

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 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 3 (if tree is balanced)
100	Up to 6 (if tree is balanced)
1000	Up to 9 (if tree is balanced)

Pattern observation: The steps grow slowly with input size if the tree is balanced, but can be as large as n if the tree is skewed.

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 the leftmost leaf.

Common Mistake

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

[OK] Correct: If the tree is not balanced, the height can be as large as the number of nodes, making the search slower.

Interview Connect

Understanding how tree shape affects search time helps you explain and improve data structure choices in real projects.

Self-Check

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