Maximum in a Binary Tree

Problem

Given a binary tree, find the maximum element present in the tree.

Examples

Example 1

Input:
  4
 / \
2   5

Output: 5

Explanation:
The elements of the tree are [4, 2, 5]. The maximum element is 5.

Example 2

Input:
        10
      /   \
     20    5
    / \
   30  35

Output: 35

Explanation:
The elements of the tree are [10, 20, 5, 30, 35]. The maximum element is 35.

Solution

Method 1 - Using Recursion

The goal is to traverse the binary tree and retrieve the maximum value from all its nodes. This can be accomplished using recursion:

1. Recursive Intuition: Start visiting nodes from the root. At each node, compare its value with the maximum values obtained from its left and right subtrees recursively.
2. Leaf Nodes: For a leaf node, its own value will be considered since there are no children.

Approach

To solve the problem:

1. Recursive Function: Define a recursive function findMax(root):
   • Base case: If the node is null, return Integer.MIN_VALUE (the smallest integer).
   • Recursive case: Find the maximum value in the left subtree and right subtree, and compare them with the current node's value.
2. Tree Traversal: The binary tree is traversed completely to ensure all elements are considered.

Code

Java

class Solution {
    // Function to find the max element
    public int findMax(TreeNode root) {
        // Base case
        if (root == null) {
            return Integer.MIN_VALUE; // If no node, return minimum integer value
        }

        // Recursive search in left and right subtrees
        int leftMax = findMax(root.left);
        int rightMax = findMax(root.right);

        // Returning the maximum among current node, left subtree, and right subtree
        return Math.max(root.val, Math.max(leftMax, rightMax));
    }

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

        // Example tree: [10, 20, 5, 30, 35]
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(20);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(30);
        root.left.right = new TreeNode(35);

        System.out.println("Max element is: " + sol.findMax(root)); // Output: 35
    }
}

Python

class Solution:
    # Function to find the max element
    def findMax(self, root):
        # Base case
        if root is None:
            return float('-inf')  # If no node, return the smallest integer value

        # Recursive search in left and right subtrees
        leftMax = self.findMax(root.left)
        rightMax = self.findMax(root.right)

        # Returning the maximum among current node, left subtree, and right subtree
        return max(root.val, leftMax, rightMax)

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

    # Example tree: [10, 20, 5, 30, 35]
    root = sol.TreeNode(10)
    root.left = sol.TreeNode(20)
    root.right = sol.TreeNode(5)
    root.left.left = sol.TreeNode(30)
    root.left.right = sol.TreeNode(35)

    print("Max element is:", sol.findMax(root))  # Output: 35

Complexity

• ⏰ Time complexity:  O(n). Every single node of the binary tree is visited once.
• 🧺 Space complexity: O(h). The recursion stack space depends on the height h of the binary tree.