BST Find Maximum Element in DSA Go - Time & Space Complexity

Time Complexity: BST Find Maximum Element

O(h)

Understanding Time Complexity

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

How does the time needed grow as the tree gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func FindMax(root *Node) *Node {
    if root == nil {
        return nil
    }
    current := root
    for current.Right != nil {
        current = current.Right
    }
    return current
}

This code finds the maximum element by moving right until no more right child exists.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Moving from one node to its right child.
• How many times: At most once per level down the right side of the tree.

How Execution Grows With Input

As the tree grows, the number of steps depends on the height of the tree, especially the rightmost path.

Input Size (n)	Approx. Operations
10	Up to 10 steps if tree is skewed right
100	Up to 100 steps in worst case
1000	Up to 1000 steps if very unbalanced

Pattern observation: The time grows with the height of the tree, which can be as small as log n or as large as n.

Final Time Complexity

Time Complexity: O(h)

This means the time depends on the tree's height, moving down the right side to find the max.

Common Mistake

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

[OK] Correct: If the tree is unbalanced and tall, it takes longer because we must follow many right children.

Interview Connect

Understanding how tree shape affects search time helps you explain and optimize tree operations clearly in interviews.

Self-Check

"What if the tree was balanced? How would the time complexity change when finding the maximum element?"