Problem

Given a non-empty binary search tree (BST), write a function to find and return the minimum data value found in the tree.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

 Input:
         10
        /  \
       5   15
      / \
     2   7
 
 Output: 
 15
 
 Explanation:
 The maximum value in the tree is found in the rightmost node, which is 15.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

 Input:
         20
        /
      15
     /
   10
 
 Output:
 20
 
 Explanation:
 The maximum value is located in the rightmost node in the tree, which is 20.

Similar Problem

Minimum in a Binary Tree Maximum in a Binary Tree Maximum in a Binary Search Tree

Solution

Method 1 - Using BST Properties

The minimum value in a BST is always found in the leftmost node, as the BST property ensures that smaller values are consistently placed on the left subtree. Thus, starting at the root and following the left child pointers until no further left child exists will yield the minimum value.

Approach

  1. Start at the root of the BST.
  2. Traverse left until you find a node that does not have a left child.
  3. The value at this node is the minimum value in the BST.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
   public int findMaximum(TreeNode root) {
       if (root == null) {
           throw new IllegalArgumentException("Tree is empty");
       }

       // Iterative traversal to the right-most node
       TreeNode current = root;
       while (current.right != null) {
           current = current.right;
       }

       return current.val; // Maximum value is in the right-most node
   }

   public static void main(String[] args) {
       // Example: Create a BST and find the maximum value
       Solution solution = new Solution();
       TreeNode root = new TreeNode(40);
       root.left = new TreeNode(30);
       root.right = new TreeNode(50);
       root.right.left = new TreeNode(45);
       root.right.right = new TreeNode(60);

       int maxValue = solution.findMaximum(root);
       System.out.println("Maximum value: " + maxValue); // Output: 60
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
   def findMaximum(self, root):
       if not root:
           raise ValueError("Tree is empty")
       
       # Iterative traversal to the right-most node
       current = root
       while current.right:
           current = current.right

       return current.val  # Maximum value is in the right-most node

# Example: Create a BST and find the maximum value
if __name__ == "__main__":
   solution = Solution()

   # Example tree
   root = TreeNode(40)
   root.left = TreeNode(30)
   root.right = TreeNode(50)
   root.right.left = TreeNode(45)
   root.right.right = TreeNode(60)

   max_value = solution.findMaximum(root)
   print("Maximum value:", max_value)  # Output: 60

Complexity

  • ⏰ Time complexity: O(h), where h is the height of the tree. For a balanced tree, the height is approximately O(log n), where n is the number of nodes. In the worst case (completely unbalanced), the height is O(n).
  • 🧺 Space complexity: O(1)