1. Problem Statement

Given a binary tree, find the maximum value among all the nodes using recursion.

2. Understanding the Problem

In a binary tree, each node has:

• A value
• A left child (can be null)
• A right child (can be null)

We need to traverse all nodes and return the maximum value present in the tree.

This tree is not necessarily a Binary Search Tree (BST), so we cannot assume any ordering between left/right subtrees.

3. Example Tree

        15
       /  \
      10   20
     / \    \
    8  12    25

Maximum Value: 25

4. Recursive Approach: Key Idea

Use postorder traversal (left → right → root) and at each node:

1. Recursively find the maximum in the left subtree
2. Recursively find the maximum in the right subtree
3. Compare both with the current node’s value
4. Return the maximum of the three

5. Base Case

If the node is null, return a value that will not interfere with max logic.

• In Java, we can return Integer.MIN_VALUE
• In Python, use float('-inf')

6. Algorithm Steps

1. If node is null → return minimum possible value
2. Recursively find max in left subtree
3. Recursively find max in right subtree
4. Return the max of: left, right, current node

7. Java Implementation

class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int val) {
        this.val = val;
    }
}


public class MaxInBinaryTree {

    public int findMax(TreeNode root) {
        if (root == null) {
            return Integer.MIN_VALUE;
        }

        int leftMax = findMax(root.left);     // max in left subtree
        int rightMax = findMax(root.right);   // max in right subtree

        // Compare left, right, and current node's value
        return Math.max(root.val, Math.max(leftMax, rightMax));
    }

    public static void main(String[] args) {
        /*
              15
             /  \
            10   20
           / \    \
          8  12    25
        */

        TreeNode root = new TreeNode(15);
        root.left = new TreeNode(10);
        root.right = new TreeNode(20);
        root.left.left = new TreeNode(8);
        root.left.right = new TreeNode(12);
        root.right.right = new TreeNode(25);

        MaxInBinaryTree tree = new MaxInBinaryTree();
        System.out.println("Maximum value in the tree: " + tree.findMax(root));  // Output: 25
    }
}

8. Step-by-Step Execution

Starting from root 15:

• Traverse left → 10
  • Traverse left → 8 → no children → return 8
  • Traverse right → 12 → no children → return 12
  • Max at node 10: max(10, 8, 12) = 12
• Traverse right → 20
  • Left is null → return Integer.MIN_VALUE
  • Right → 25 → no children → return 25
  • Max at node 20: max(20, MIN, 25) = 25
• Max at root 15: max(15, 12, 25) = 25

9. Visual Diagram (Text)

              15
            /    \
          10      20
         /  \       \
        8   12       25

Postorder Flow:
- visit 8 → return 8
- visit 12 → return 12
- at 10 → max(10, 8, 12) = 12
- visit 25 → return 25
- at 20 → max(20, MIN, 25) = 25
- at 15 → max(15, 12, 25) = 25

10. Time and Space Complexity

Measure	Value
Time Complexity	O(n) – visit every node once
Space Complexity	O(h) – recursion stack height
Best case	O(log n) for balanced tree
Worst case	O(n) for skewed tree

11. Edge Cases

Case	Return Value
Empty Tree (null)	Integer.MIN_VALUE (or equivalent)
One Node (val = X)	X
All Negative Values	Will return highest negative