AlgoViz
HomeBinary Search Trees

Find Min/Max in BST

Easy

Walk hard left, or hard right

Problem

Return the minimum and maximum values in a BST.

In simple words

The smallest value is the leftmost node, the largest is the rightmost — just keep turning that way.

The idea

The smallest value has nothing to its left, so following left pointers until null lands on it; the largest is the mirror image on the right. No comparisons are needed at all — only the structure.

The trick

  • Leftmost node is the minimum, rightmost is the maximum.
  • O(height) with O(1) space.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

5
3
8
1
4
7
9
0
1
2
3
4
5
6

Step 1 of 2. Here's the example — [5,3,8,1,4,7,9] Values: 5, 3, 8, 1, 4, 7, 9.

1/2
Optimal
timeO(h)spaceO(1)
1min: walk left until node.left is null2max: walk right until node.right is null

Input

array
[5, 3, 8, 1, 4, 7, 9]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
bst = [8,4,12,2,6,10,14]
Output:
[2, 14]
Explanation:
Leftmost is min, rightmost is max.

Example 2

Input:
bst = [5]
Output:
[5, 5]
Explanation:
One node is both.

Example 3

Input:
bst = [3,1,5]
Output:
[1, 5]
Explanation:
Min 1, max 5.

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.