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

Time Complexity: BST Find Maximum Element

O(h)

Understanding Time Complexity

Finding the maximum element in a Binary Search Tree (BST) involves moving through the tree nodes.

We want to know how the time to find this maximum grows as the tree gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function findMax(root: TreeNode | null): number | null {
  if (root === null) return null;
  let current = root;
  while (current.right !== null) {
    current = current.right;
  }
  return current.val;
}
    

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 in a loop.
• How many times: At most once per level down the right side of the tree.

How Execution Grows With Input

Each step moves one node to the right until the last node is reached.

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 in worst case

Pattern observation: The number of steps grows linearly with the height of the tree's right side.

Final Time Complexity

Time Complexity: O(h)

This means the time depends on the height of the tree, moving down the right side nodes.

Common Mistake

[X] Wrong: "Finding max is always O(log n) because BSTs are balanced."

[OK] Correct: Not all BSTs are balanced; if the tree is skewed, height can be as large as n, making it slower.

Interview Connect

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

Self-Check

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