Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Minimum & Maximum in a BST

MEDIUMProblemSolveExternal Links

Description

Given the root of a Binary Search Tree (BST), find the minimum and maximum values present in the tree.

Return both values.

Recall that in a BST:

  • The left subtree of every node contains only values smaller than the node's value
  • The right subtree of every node contains only values greater than the node's value
  • Both subtrees are themselves BSTs

This ordering means the smallest value is always found by walking as far left as possible, and the largest value by walking as far right as possible.

Examples

Example 1

Input:

        5
       / \
      3   8
     / \   \
    1   4   10

Output: min = 1, max = 10

Explanation: The leftmost node is 1 (following the path 5 → 3 → 1). No node has a smaller value because every step to the left takes us to a smaller value in a BST. The rightmost node is 10 (following the path 5 → 8 → 10). No node has a larger value.

Example 2

Input:

    6
   / \
  5   8
 /
2

Output: min = 2, max = 8

Explanation: The leftmost path is 6 → 5 → 2. Node 2 has no left child, so 2 is the minimum. The rightmost path is 6 → 8. Node 8 has no right child, so 8 is the maximum.

Example 3

Input:

    4

Output: min = 4, max = 4

Explanation: A single-node tree. The root is both the leftmost and rightmost node, so the minimum and maximum are both 4.

Constraints

  • 1 ≤ Number of nodes ≤ 10^5
  • 1 ≤ Node.val ≤ 10^5
  • root is a valid binary search tree

Editorial

Brute Force

Intuition

The most straightforward way to find the minimum and maximum is to collect every value in the tree and then pick the smallest and largest. Since inorder traversal of a BST yields values in sorted ascending order, the first element of the inorder result is the minimum and the last element is the maximum.

Think of it like reading every page in a sorted notebook from beginning to end: the first page holds the smallest number, and the last page holds the largest. You read every page even though you only need the first and last.

This approach works for any binary tree (not just BSTs), since it collects all values and takes the extremes. However, it ignores the BST structure entirely — we store all n values in a list just to read two of them.

Step-by-Step Explanation

Let's trace through with the BST:

        5
       / \
      3   8
     / \   \
    1   4   10

Step 1: Initialize an empty list sorted_vals = [].

Step 2: Start inorder traversal. Go as far left as possible: 5 → 3 → 1. Node 1 has no left child.

Step 3: Visit node 1 (no left child). Append 1. sorted_vals = [1].

Step 4: Backtrack to node 3. Append 3. sorted_vals = [1, 3].

Step 5: Visit right child of 3: node 4. Append 4. sorted_vals = [1, 3, 4].

Step 6: Backtrack to root 5. Append 5. sorted_vals = [1, 3, 4, 5].

Step 7: Visit right subtree of 5: node 8. Append 8. sorted_vals = [1, 3, 4, 5, 8].

Step 8: Visit right child of 8: node 10. Append 10. sorted_vals = [1, 3, 4, 5, 8, 10].

Step 9: Inorder complete. min = sorted_vals[0] = 1, max = sorted_vals[-1] = 10.

Inorder Traversal — Collecting All Values to Find Min and Max — Watch the inorder traversal visit every node in sorted order. We collect all values into a list, then simply read the first and last elements.

Algorithm

  1. Perform an inorder traversal of the BST, collecting all node values into a list
  2. The inorder traversal of a BST produces values in sorted ascending order
  3. The minimum is the first element of the sorted list
  4. The maximum is the last element of the sorted list
  5. Return both values

Code

#include <vector>
#include <utility>
using namespace std;

class Solution {
public:
    pair<int, int> findMinMax(TreeNode* root) {
        vector<int> sortedVals;
        inorder(root, sortedVals);
        
        int minVal = sortedVals.front();
        int maxVal = sortedVals.back();
        return {minVal, maxVal};
    }

private:
    void inorder(TreeNode* node, vector<int>& result) {
        if (node == nullptr) return;
        inorder(node->left, result);
        result.push_back(node->val);
        inorder(node->right, result);
    }
};
from typing import Optional, Tuple

class Solution:
    def findMinMax(self, root: Optional[TreeNode]) -> Tuple[int, int]:
        sorted_vals = []
        
        def inorder(node):
            if not node:
                return
            inorder(node.left)
            sorted_vals.append(node.val)
            inorder(node.right)
        
        inorder(root)
        return (sorted_vals[0], sorted_vals[-1])
import java.util.*;

class Solution {
    public int[] findMinMax(TreeNode root) {
        List<Integer> sortedVals = new ArrayList<>();
        inorder(root, sortedVals);
        
        int minVal = sortedVals.get(0);
        int maxVal = sortedVals.get(sortedVals.size() - 1);
        return new int[]{minVal, maxVal};
    }
    
    private void inorder(TreeNode node, List<Integer> result) {
        if (node == null) return;
        inorder(node.left, result);
        result.add(node.val);
        inorder(node.right, result);
    }
}

Complexity Analysis

Time Complexity: O(n)

The inorder traversal visits every node exactly once, where n is the number of nodes in the BST. Each visit performs O(1) work (appending to the list). After traversal, reading the first and last elements is O(1).

Space Complexity: O(n)

The sorted list stores all n node values. Additionally, the recursion stack uses O(h) space where h is the tree height. Total: O(n + h) = O(n) since h ≤ n.

Why This Approach Is Not Efficient

The inorder traversal approach visits all n nodes and stores all n values in memory, even though we only need two values: the minimum and the maximum.

For a BST with n = 100,000 nodes, we allocate a list of 100,000 integers (roughly 400 KB of memory) just to read the first and last entries. The other 99,998 values are collected and then discarded — a massive waste of both time and space.

The fundamental insight we are ignoring: in a BST, the minimum is always the leftmost node (keep going left from root until there is no left child), and the maximum is always the rightmost node (keep going right until there is no right child). We do not need to visit the nodes in between.

Finding the leftmost node requires visiting at most h nodes (one per level along the left edge), and finding the rightmost node requires at most h nodes along the right edge. For a balanced BST with 100,000 nodes, h ≈ 17 — meaning we could find both extremes by visiting ~34 nodes instead of 100,000.

Better Approach - Recursive BST Property

Intuition

The BST property gives us a direct path to both extremes:

  • Minimum: Start at the root and keep moving to the left child. When a node has no left child, that node holds the smallest value in the entire tree. Why? Because in a BST, every value in a node's left subtree is smaller than the node itself. The node with no left child has no smaller values beneath it — it IS the smallest.

  • Maximum: Start at the root and keep moving to the right child. When a node has no right child, that node holds the largest value. Same logic: every value in a node's right subtree is larger, so the node with no right subtree is the largest.

Think of it like finding the shortest and tallest person in a line that is already sorted by height. You do not need to check everyone — just look at the person at the front (minimum) and the person at the back (maximum).

The recursive version expresses this as two simple functions: one that recurses left until it reaches a dead end, and one that recurses right.

Step-by-Step Explanation

Let's trace through with the BST:

        5
       / \
      3   8
     / \   \
    1   4   10

Finding Minimum (recurse left):

Step 1: Start at root node 5. Does node 5 have a left child? Yes (node 3). Recurse left.

Step 2: At node 3. Does node 3 have a left child? Yes (node 1). Recurse left.

Step 3: At node 1. Does node 1 have a left child? No. This is the leftmost node. min = 1.

Finding Maximum (recurse right):

Step 4: Start at root node 5 again. Does node 5 have a right child? Yes (node 8). Recurse right.

Step 5: At node 8. Does node 8 have a right child? Yes (node 10). Recurse right.

Step 6: At node 10. Does node 10 have a right child? No. This is the rightmost node. max = 10.

Result: min = 1, max = 10. We visited only 6 nodes total (3 for min path + 3 for max path), and we never touched nodes 4 at all.

Recursive BST Min/Max — Walking the Left and Right Edges — Watch two separate recursive walks: one traces the left edge to find the minimum, then the other traces the right edge to find the maximum.

Algorithm

Finding Minimum:

  1. If root has no left child, return root.val (this is the minimum)
  2. Otherwise, recursively call findMin(root.left)

Finding Maximum:

  1. If root has no right child, return root.val (this is the maximum)
  2. Otherwise, recursively call findMax(root.right)

Combined:

  1. Call findMin(root) to get the minimum
  2. Call findMax(root) to get the maximum
  3. Return both values

Code

#include <utility>
using namespace std;

class Solution {
public:
    pair<int, int> findMinMax(TreeNode* root) {
        int minVal = findMin(root);
        int maxVal = findMax(root);
        return {minVal, maxVal};
    }

private:
    int findMin(TreeNode* node) {
        // No left child → this is the minimum
        if (node->left == nullptr)
            return node->val;
        return findMin(node->left);
    }
    
    int findMax(TreeNode* node) {
        // No right child → this is the maximum
        if (node->right == nullptr)
            return node->val;
        return findMax(node->right);
    }
};
from typing import Optional, Tuple

class Solution:
    def findMinMax(self, root: Optional[TreeNode]) -> Tuple[int, int]:
        min_val = self._find_min(root)
        max_val = self._find_max(root)
        return (min_val, max_val)
    
    def _find_min(self, node: TreeNode) -> int:
        # No left child → this is the minimum
        if not node.left:
            return node.val
        return self._find_min(node.left)
    
    def _find_max(self, node: TreeNode) -> int:
        # No right child → this is the maximum
        if not node.right:
            return node.val
        return self._find_max(node.right)
class Solution {
    public int[] findMinMax(TreeNode root) {
        int minVal = findMin(root);
        int maxVal = findMax(root);
        return new int[]{minVal, maxVal};
    }
    
    private int findMin(TreeNode node) {
        // No left child → this is the minimum
        if (node.left == null)
            return node.val;
        return findMin(node.left);
    }
    
    private int findMax(TreeNode node) {
        // No right child → this is the maximum
        if (node.right == null)
            return node.val;
        return findMax(node.right);
    }
}

Complexity Analysis

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

Finding the minimum traverses at most h nodes along the left edge. Finding the maximum traverses at most h nodes along the right edge. Total: O(h + h) = O(h). For a balanced BST, h = O(log n). For a skewed BST, h = O(n).

Space Complexity: O(h)

Each recursive call (findMin or findMax) adds one frame to the call stack. The maximum recursion depth is h (one call per level along the left or right edge). For a balanced tree, this is O(log n). For a completely left-skewed tree, findMin would use O(n) stack space.

Why This Approach Is Not Efficient

The recursive approach achieves O(h) time — a dramatic improvement over O(n). But it still uses O(h) space for the recursion call stack.

Consider a completely left-skewed BST (every node has only a left child — essentially a sorted linked list going down-left). With n = 100,000 nodes, findMin would recurse 100,000 levels deep, creating 100,000 stack frames. In many language runtimes, this causes a stack overflow.

The recursion here is tail recursion — the recursive call is the last operation in the function, and its result is returned directly without modification. The function does not need to remember anything from the current call after making the recursive call. This is a classic candidate for conversion to a while loop, which eliminates the stack overhead entirely.

The insight: walking to the leftmost or rightmost node is a straight-line path — no branching, no backtracking. A simple while loop can follow this path using only a single pointer variable, achieving O(1) extra space.

Optimal Approach - Iterative Left/Right Walk

Intuition

Finding the minimum and maximum in a BST boils down to two independent straight-line walks:

  1. Minimum: Start a pointer at root. While the pointer has a left child, move it left. When it stops, it points to the minimum.
  2. Maximum: Start a pointer at root. While the pointer has a right child, move it right. When it stops, it points to the maximum.

Each walk is a simple while loop — no recursion, no stack, no extra memory beyond a single pointer. The pointer slides along the left (or right) edge of the tree like a finger tracing the edge of a staircase: always stepping in one direction until there are no more steps.

This is the most direct possible solution: we go exactly where the answer is, using the minimum possible resources.

Step-by-Step Explanation

Let's trace through with the BST:

        5
       / \
      3   8
     / \   \
    1   4   10

Finding Minimum (while loop going left):

Step 1: Set curr = root (node 5). curr has a left child (node 3).

Step 2: Move curr to curr.left → node 3. curr has a left child (node 1).

Step 3: Move curr to curr.left → node 1. curr has NO left child. Loop ends. min = curr.val = 1.

Finding Maximum (while loop going right):

Step 4: Reset curr = root (node 5). curr has a right child (node 8).

Step 5: Move curr to curr.right → node 8. curr has a right child (node 10).

Step 6: Move curr to curr.right → node 10. curr has NO right child. Loop ends. max = curr.val = 10.

Result: min = 1, max = 10. Two while loops, each running 3 iterations. Zero extra space used.

Iterative Left/Right Walk — O(1) Space Min/Max — Watch a single pointer slide left to find the minimum, then slide right to find the maximum. No recursion stack — just two while loops.

Algorithm

Finding Minimum:

  1. Set curr = root
  2. While curr.left is not null, set curr = curr.left
  3. Return curr.val (this is the minimum)

Finding Maximum:

  1. Set curr = root
  2. While curr.right is not null, set curr = curr.right
  3. Return curr.val (this is the maximum)

Combined:

  1. Run the minimum-finding while loop
  2. Run the maximum-finding while loop
  3. Return both values

Code

#include <utility>
using namespace std;

class Solution {
public:
    pair<int, int> findMinMax(TreeNode* root) {
        int minVal = findMin(root);
        int maxVal = findMax(root);
        return {minVal, maxVal};
    }

private:
    int findMin(TreeNode* root) {
        TreeNode* curr = root;
        while (curr->left != nullptr) {
            curr = curr->left;
        }
        return curr->val;
    }
    
    int findMax(TreeNode* root) {
        TreeNode* curr = root;
        while (curr->right != nullptr) {
            curr = curr->right;
        }
        return curr->val;
    }
};
from typing import Optional, Tuple

class Solution:
    def findMinMax(self, root: Optional[TreeNode]) -> Tuple[int, int]:
        min_val = self._find_min(root)
        max_val = self._find_max(root)
        return (min_val, max_val)
    
    def _find_min(self, root: TreeNode) -> int:
        curr = root
        while curr.left:
            curr = curr.left
        return curr.val
    
    def _find_max(self, root: TreeNode) -> int:
        curr = root
        while curr.right:
            curr = curr.right
        return curr.val
class Solution {
    public int[] findMinMax(TreeNode root) {
        int minVal = findMin(root);
        int maxVal = findMax(root);
        return new int[]{minVal, maxVal};
    }
    
    private int findMin(TreeNode root) {
        TreeNode curr = root;
        while (curr.left != null) {
            curr = curr.left;
        }
        return curr.val;
    }
    
    private int findMax(TreeNode root) {
        TreeNode curr = root;
        while (curr.right != null) {
            curr = curr.right;
        }
        return curr.val;
    }
}

Complexity Analysis

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

The minimum-finding loop runs at most h iterations (one per level along the left edge). The maximum-finding loop runs at most h iterations (one per level along the right edge). Total: O(h + h) = O(h). For a balanced BST with n = 100,000 nodes, h ≈ 17, so we do about 34 iterations total. For a skewed BST, h = n in the worst case.

Space Complexity: O(1)

We use only a single pointer variable curr (reused for both walks). No recursion stack, no auxiliary data structures. This is the optimal space complexity — you cannot find the min and max without at least reading the root, which is O(1).