Problem

Given a binary tree, find the minimum element present in it.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

 Input: 
        10
       /  \
      5    20
     / \   / \
    2   8 15 25
 
 Output: 2
 
 Explanation: The minimum value from all nodes (10, 5, 20, 2, 8, 15, 25) is 2.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

 Input: 
       15
      /  \
     12    20
    /         \
   10          25
 
 Output: 10
 
 Explanation: The minimum value from all nodes (15, 12, 20, 10, 25) is 10.

Similar Problem

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

Solution

We can use either Depth First Search (DFS) or Breadth First Search (BFS) to traverse the tree.

Method 1 - DFS

Here is the approach:

  • Implement a helper function to recursively traverse left and right subtrees.
  • Maintain and return the minimum value observed during traversal.

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


public class Solution {
    public int findMin(TreeNode root) {
        if (root == null) {
            return Integer.MAX_VALUE; // Base case for empty node
        }
        
        // Recursive DFS to find the minimum element in the tree
        int leftMin = findMin(root.left);
        int rightMin = findMin(root.right);
        
        return Math.min(root.val, Math.min(leftMin, rightMin));
    }

    public static void main(String[] args) {
        // Runner code
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(5);
        root.right = new TreeNode(20);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(8);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(25);

        Solution solver = new Solution();
        System.out.println(solver.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

class Solution:
    def findMin(self, root):
        if not root:
            return float('inf')  # Base case for empty node
        
        # Recursive DFS to find the minimum element in the tree
        left_min = self.findMin(root.left)
        right_min = self.findMin(root.right)
        
        return min(root.val, left_min, right_min)

# Runner code
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(20)
root.left.left = TreeNode(2)
root.left.right = TreeNode(8)
root.right.left = TreeNode(15)
root.right.right = TreeNode(25)

solver = Solution()
print(solver.findMin(root))  # Output: 2

Complexity

  • ⏰ Time complexity: O(n). As we visit all n nodes in the binary tree.
  • 🧺 Space complexity: O(h) in the recursive approach.

Method 2 - Level Order Traversal

Here is the approach:

  1. Initialise a queue and insert the root node as the starting point.
  2. While the queue is not empty:
    • Poll the front node (i.e., process the node at the front of the queue).
    • Compare the value of the current node with the smallest value seen so far.
    • Add the left and right children (if any) of the current node to the queue.
  3. At the end of traversal, return the smallest 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
30
31
32
33
34
35
36
37
38
39
40

public class Solution {
    public int findMin(TreeNode root) {
        if (root == null) {
            return Integer.MAX_VALUE; // Base case for empty tree
        }
        
        // BFS implementation using a queue
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int minVal = Integer.MAX_VALUE;
        
        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            minVal = Math.min(minVal, current.val);
            
            if (current.left != null) {
                queue.add(current.left);
            }
            if (current.right != null) {
                queue.add(current.right);
            }
        }
        
        return minVal;
    }

    public static void main(String[] args) {
        // Runner code
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(5);
        root.right = new TreeNode(20);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(8);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(25);

        Solution solver = new Solution();
        System.out.println(solver.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
25
26
27
28
29
30
31

class Solution:
    def findMin(self, root):
        if not root:
            return float('inf')  # Base case for empty tree
        
        # BFS implementation using a queue
        queue = [root]
        min_val = float('inf')
        
        while queue:
            current = queue.pop(0)
            min_val = min(min_val, current.val)
            
            if current.left:
                queue.append(current.left)
            if current.right:
                queue.append(current.right)
        
        return min_val

# Runner code
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(20)
root.left.left = TreeNode(2)
root.left.right = TreeNode(8)
root.right.left = TreeNode(15)
root.right.right = TreeNode(25)

solver = Solution()
print(solver.findMin(root))  # Output: 2

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)