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: 
 2
 
 Explanation:
 The smallest value in the tree is found in the leftmost node, which is 2.

Example 2

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

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

Similar Problem

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

Solution

Method 1 - Using BST Properties

In a Binary Search Tree, the largest value will always be in the rightmost leaf node, since values increase as you traverse to the right.

Approach

  1. Start at the root node.
  2. Traverse the tree iteratively (or recursively), moving to the right child as long as it exists.
  3. When you reach a node with no right child, that node contains the maximum value.

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
29

class Solution {
    // Method to find the minimum value in the BST
    public int findMin(TreeNode root) {
        if (root == null) {
            throw new IllegalArgumentException("Tree must contain at least one node.");
        }

        TreeNode current = root;
        while (current.left != null) {
            current = current.left; // Traverse left until no left child exists
        }
        return current.val; // Return the value of the leftmost node
    }

    // Example usage
    public static void main(String[] args) {
        Solution solution = new Solution();

        // Example Input: Constructing the BST
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(5);
        root.right = new TreeNode(15);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(7);

        // Output: Find minimum value
        System.out.println("Minimum value in BST: " + solution.findMin(root)); // Output: 2
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def findMin(self, root):
        if not root:
            raise ValueError("Tree must contain at least one node.")
        
        current = root
        while current.left:
            current = current.left  # Traverse left until no left child exists
        return current.val  # Return the value of the leftmost node


# Example usage
if __name__ == "__main__":
    solution = Solution()

    # Example Input: Constructing the BST
    root = TreeNode(10)
    root.left = TreeNode(5)
    root.right = TreeNode(15)
    root.left.left = TreeNode(2)
    root.left.right = TreeNode(7)

    # Output: Find minimum value
    print("Minimum value in BST:", solution.findMin(root)) # Output: 2

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)