Binary Search TreesProblem 3 of 22
Find min and max value in a BST
Problem Statement
Given a Binary Search Tree, find the minimum and maximum values in the tree.
Example:
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
Minimum Value: 1 (leftmost node)
Maximum Value: 14 (rightmost node)
Approach 1: Brute Force (Traverse Entire Tree)
Intuition
Traverse all nodes of the tree and keep track of minimum and maximum values encountered. This ignores the BST property.
Algorithm
- Initialize min as infinity and max as negative infinity
- Traverse all nodes using any traversal method
- Update min and max at each node
- Return the final min and max values
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private int minVal = Integer.MAX_VALUE;
private int maxVal = Integer.MIN_VALUE;
private void traverseBruteForce(TreeNode root) {
if (root == null) return;
minVal = Math.min(minVal, root.val);
maxVal = Math.max(maxVal, root.val);
traverseBruteForce(root.left);
traverseBruteForce(root.right);
}
public int[] findMinMaxBruteForce(TreeNode root) {
if (root == null) return new int[]{};
minVal = Integer.MAX_VALUE;
maxVal = Integer.MIN_VALUE;
traverseBruteForce(root);
return new int[]{minVal, maxVal};
}
}Complexity Analysis
- Time Complexity: O(n) - Visit all nodes
- Space Complexity: O(n) - Recursion stack for skewed tree
Approach 2: Optimal (Using BST Property - Recursive)
Intuition
In a BST:
- The minimum value is at the leftmost node
- The maximum value is at the rightmost node
Algorithm
For Minimum:
- Keep going left until left child is null
- Return current node's value
For Maximum:
- Keep going right until right child is null
- Return current node's value
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
// Find minimum (recursive)
public int findMinRecursive(TreeNode root) {
if (root == null) {
throw new IllegalArgumentException("Tree is empty");
}
if (root.left == null) {
return root.val;
}
return findMinRecursive(root.left);
}
// Find maximum (recursive)
public int findMaxRecursive(TreeNode root) {
if (root == null) {
throw new IllegalArgumentException("Tree is empty");
}
if (root.right == null) {
return root.val;
}
return findMaxRecursive(root.right);
}
}Complexity Analysis
- Time Complexity: O(h) where h is height - O(log n) for balanced, O(n) for skewed
- Space Complexity: O(h) - Recursion stack
Approach 3: Optimal (Iterative - Best Space)
Intuition
Same logic as recursive but using iteration to avoid recursion stack, achieving O(1) space.
Algorithm
- For minimum: Keep moving left until null
- For maximum: Keep moving right until null
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
// Find minimum (iterative)
public int findMin(TreeNode root) {
if (root == null) {
throw new IllegalArgumentException("Tree is empty");
}
TreeNode curr = root;
while (curr.left != null) {
curr = curr.left;
}
return curr.val;
}
// Find maximum (iterative)
public int findMax(TreeNode root) {
if (root == null) {
throw new IllegalArgumentException("Tree is empty");
}
TreeNode curr = root;
while (curr.right != null) {
curr = curr.right;
}
return curr.val;
}
// Find both min and max
public int[] findMinMax(TreeNode root) {
return new int[]{findMin(root), findMax(root)};
}
}Complexity Analysis
- Time Complexity: O(h) where h is height
- Space Complexity: O(1) - Only using pointers
Key Takeaways
- BST Property: Min is leftmost, max is rightmost
- Iterative is better: O(1) space vs O(h) for recursive
- Height dependent: O(log n) for balanced, O(n) for skewed
- Edge case: Handle empty tree
- These operations are building blocks for other BST operations
- Finding min is used in deletion (finding inorder successor)
- Finding max is used in finding inorder predecessor