BST Find Maximum Element in DSA C++ - 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 biggest number in a Binary Search Tree (BST).

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

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Find maximum value in a BST
int findMax(Node* root) {
    if (root == nullptr) return -1; // empty tree
    Node* current = root;
    while (current->right != nullptr) {
        current = current->right;
    }
    return current->data;
}
    

This code moves right in the tree until it finds the largest value, which is the rightmost node.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Moving from one node to its right child.
• How many times: Up to the height of the tree (number of right edges).

How Execution Grows With Input

As the tree grows taller, the number of steps to reach the rightmost node grows roughly with the tree height.

Input Size (n)	Approx. Operations (steps to rightmost node)
10	Up to 10 (if tree is a straight line)
100	Up to 100 (worst case)
1000	Up to 1000 (worst case)

Pattern observation: The time grows linearly with the height of the tree, which can be as big as the number of nodes in the worst case.

Final Time Complexity

Time Complexity: O(h) where h is the height of the BST.

This means the time depends on how tall the tree is, not just how many nodes it has.

Common Mistake

[X] Wrong: "Finding the max in a BST always takes the same time no matter the tree size."

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

Interview Connect

Knowing how tree shape affects search time helps you explain and improve data structures in real projects.

Self-Check

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