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

Time Complexity: BST Find Maximum Element

O(h)

Understanding Time Complexity

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

Specifically, how does the time grow as the tree gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function findMax(root) {
  if (!root) return null;
  let current = root;
  while (current.right !== null) {
    current = current.right;
  }
  return current.value;
}
    

This code finds the maximum value 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 rightmost path.

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

Pattern observation: The steps grow slowly with tree height, not total nodes.

Final Time Complexity

Time Complexity: O(h)

This means the time depends on the tree height, which is the longest path from root to leaf.

Common Mistake

[X] Wrong: "Finding max always takes time proportional to the number of nodes (n)."

[OK] Correct: We only follow the right children, so time depends on tree height, not total nodes.

Interview Connect

Understanding how tree height affects search time helps you explain efficiency clearly in interviews.

Self-Check

"What if the BST is unbalanced and looks like a linked list? How would the time complexity change?"