Max and Min element in binary tree

Problem Link

Max and Min Element in Binary Tree – GeeksforGeeks

Problem: Max and Min Element in Binary Tree

Problem Statement

Given a binary tree, find the maximum and minimum elements in it.

Examples

Example 1
Input:

     1
    / \
   2   3

Output: Max = 3, Min = 1

Example 2
Input:

Output: Max = 20, Min = 1

Constraints

1 <= Number of nodes <= 10⁴
-10⁵ <= Node value <= 10⁵

Intuition

We need to traverse the entire tree and find the maximum and minimum values among all nodes.

This can be easily done via recursion:

At each node:
- Ask left and right subtree their max and min
- Compare with the current node's value
- Return overall max/min upward

Approach (Recursion using Induction – Base Case – Hypothesis)

1. Base Case:

If the node is null:

For max: return Integer.MIN_VALUE
For min: return Integer.MAX_VALUE

2. Hypothesis:

Assume we have correctly found maxLeft, maxRight and similarly minLeft, minRight.

3. Induction:

Use Math.max and Math.min to return the correct value including current node.

Code (Java)

class Tree {
    // Function to find the maximum element in Binary Tree
    int findMax(Node root) {
        if (root == null) return Integer.MIN_VALUE;

        int leftMax = findMax(root.left);
        int rightMax = findMax(root.right);

        return Math.max(root.data, Math.max(leftMax, rightMax));
    }

    // Function to find the minimum element in Binary Tree
    int findMin(Node root) {
        if (root == null) return Integer.MAX_VALUE;

        int leftMin = findMin(root.left);
        int rightMin = findMin(root.right);

        return Math.min(root.data, Math.min(leftMin, rightMin));
    }
}

Time and Space Complexity

Time Complexity: O(N)
Each node is visited once.
Space Complexity: O(H)
Due to recursion stack, where H is the height of the tree (O(log N) for balanced, O(N) for skewed).

Dry Run

Input:

findMax(10) → max(10, findMax(20), findMax(5))
→ max(10, 20, 5) = 20

findMin(10) → min(10, findMin(20), findMin(5))
→ min(10, 1, 5) = 1

Conclusion

This is a direct and elegant application of divide and conquer using recursion. It demonstrates:

Post-order traversal
Recursive min/max comparisons
How to think recursively in trees