Finding the maximum node in a Binary Tree - Two methods (Java)

Finding the largest value in a binary tree is one of the first tree problems most people solve, and it is a good one to get comfortable with, because the same two patterns (a queue for level order, recursion for depth first) come back in almost every tree question after it.

Note that this is a plain binary tree, not a binary search tree. In a BST you could just keep walking right until you hit the last node. Here the values can be anywhere, so we have to look at every node.

Problem

Given the root of a binary tree, return the maximum value stored in any node. For the tree below the answer is 70.

          10
        /    \
      20      30
     /  \    /  \
   40   50  60   70

Method 1: level order traversal with a queue

Put the root in a queue. Then keep taking a node out of the front, compare its value with the best so far, and push its children to the back. When the queue is empty, every node has been seen once and the variable holds the answer.

The earlier version of this post stored every value in a list and called Collections.max() at the end. That works, but it uses an extra list for no reason. Keeping a running maximum is simpler and saves memory.

Method 2: recursion

The largest value in a tree is the biggest of three numbers: the root's own value, the largest value in the left subtree and the largest value in the right subtree. That sentence is the whole algorithm. The base case is an empty subtree, for which we return Integer.MIN_VALUE so it never wins a comparison.

Trace it on the tree above. The call on 40 returns 40 (both children are empty). The call on 20 returns max(20, 40, 50) = 50. The right side gives max(30, 60, 70) = 70. Finally the root returns max(10, 50, 70) = 70.

Solution in Java (both methods)

import java.util.LinkedList;
import java.util.Queue;

class Node {
    int data;
    Node left, right;
    Node(int data) { this.data = data; }
}

public class MaxNode {
    // Method 1: level order traversal with a queue
    static int maxIterative(Node root) {
        if (root == null) return Integer.MIN_VALUE;
        int max = Integer.MIN_VALUE;
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            Node curr = q.poll();
            max = Math.max(max, curr.data);
            if (curr.left != null) q.add(curr.left);
            if (curr.right != null) q.add(curr.right);
        }
        return max;
    }

    // Method 2: recursion
    static int maxRecursive(Node root) {
        if (root == null) return Integer.MIN_VALUE;
        return Math.max(root.data, Math.max(maxRecursive(root.left), maxRecursive(root.right)));
    }

    public static void main(String[] args) {
        //          10
        //        /    \
        //      20      30
        //     /  \    /  \
        //   40   50  60   70
        Node root = new Node(10);
        root.left = new Node(20);
        root.right = new Node(30);
        root.left.left = new Node(40);
        root.left.right = new Node(50);
        root.right.left = new Node(60);
        root.right.right = new Node(70);

        System.out.println(maxIterative(root));
        System.out.println(maxRecursive(root));
    }
}

Output

70
70

Complexity

• Time: O(n) for both methods, since each node is visited once.
• Space: the queue in method 1 can hold a whole level, which is up to about n/2 nodes in a full tree. Recursion in method 2 uses stack space equal to the height of the tree: O(log n) for a balanced tree, but O(n) for a tree that is basically a linked list.

Things to watch out for

• Returning -1 for an empty tree, as many solutions do, breaks as soon as the tree contains negative numbers. Integer.MIN_VALUE is the safer choice, or throw an exception if an empty tree is not allowed.
• For a very deep, skewed tree (say 100,000 nodes in a line), the recursive version can throw a StackOverflowError. The queue version does not have that problem.
• The minimum value works the same way: swap max for min and MIN_VALUE for MAX_VALUE.

Next, try the inorder, preorder and postorder traversals, or test yourself with the trees and BST MCQs.

Tip: try to solve the problem yourself before reading the solution. Use the code as a reference to check your approach, and make sure you understand why it works.

More data structures tutorials All coding problems MCQ practice