Recursively find the maximum node of a binary tree

You're in a technical phone screen and the interviewer asks you to find the largest value in a binary tree. It sounds simple enough, but this question is really testing whether you can think recursively about tree structures. This problem, also known as "Find Maximum Value in Binary Tree" on other platforms, is a staple warm-up that builds toward harder tree problems like max path sum and tree diameter.

TL;DR

Recursively traverse the binary tree, comparing each node's data with the maximum values found in its left and right subtrees. The base case returns Integer.MIN_VALUE for null nodes so they never affect the comparison. This visits every node once for O(n) time and uses O(log n) stack space on a balanced tree.

Why This Problem Matters

Finding the maximum node in a binary tree teaches the foundational "combine subtree results" pattern that appears in nearly every recursive tree problem. The same structure, solve left, solve right, combine at the current node, applies to finding tree height, computing sums, checking balance, and calculating diameter. Get comfortable with this pattern and tree problems stop feeling intimidating.

Prefer a different language? Jump to solutions in other languages.

Binary Trees: A Quick Refresher

A binary tree is a hierarchical data structure where each node has at most two children. Unlike a binary search tree, a general binary tree imposes no ordering on its values. The maximum could be at the root, a leaf, or anywhere in between.

Key terminology:

• Root: The topmost node (node 1 above)
• Leaf: A node with no children (nodes 2, 4, and 5)
• Subtree: Any node plus all its descendants

Because there's no ordering guarantee, finding the maximum requires visiting every node.

Understanding the Problem

Given: The root TreeNode of a binary tree Return: The maximum data value of any node in the tree Constraints: The tree has 1 to 100 nodes, each with data between -1000 and 1000

Here's our example tree with the maximum highlighted:

For this tree, maxData(root) returns 5. The algorithm needs to compare all five node values and determine that 5 is the largest.

Edge Cases to Consider

1. Single node: The root's data is the maximum
2. All negative values: The algorithm must still find the correct (least negative) value
3. Skewed tree: All nodes on one side, essentially a linked list
4. Maximum at the root: The algorithm should not assume the max is always in a subtree

The all-negative case is particularly important because it determines your choice of base case value.

Solution Approach

Think about this recursively. If you're standing at any node, the maximum value in the tree rooted at that node is the largest of three candidates:

1. The current node's data
2. The maximum in the left subtree
3. The maximum in the right subtree

That gives us a clean recursive formula:

maxData(node) = max(node.data, maxData(node.left), maxData(node.right))

For the base case, when we reach a null node (past a leaf), we need a value that will never win any comparison. Integer.MIN_VALUE serves this purpose perfectly. If we returned 0 instead, a tree full of negative values would incorrectly report 0 as the maximum.

Walking Through the Example

Let's trace through the tree [1, 2, 3, #, #, 4, 5]:

The recursion unfolds depth-first:

1. Visit node 1, recurse into left child (node 2)
2. Node 2 is a leaf. Both children are null, returning MIN_VALUE. max(2, MIN, MIN) = 2
3. Back at node 1, recurse into right child (node 3)
4. Node 3 recurses left to node 4 (leaf, returns 4) and right to node 5 (leaf, returns 5)
5. Node 3 computes max(3, 4, 5) = 5
6. Node 1 computes max(1, 2, 5) = 5

The answer is 5.

Implementation

public class Solution {
  public int maxData(TreeNode root) {
    // Base case: null node returns the smallest possible value
    if (root == null) return Integer.MIN_VALUE;

    // Recursively find the max in each subtree
    int leftMax = maxData(root.left);
    int rightMax = maxData(root.right);

    // The max for this subtree is the largest of all three candidates
    return Math.max(root.data, Math.max(leftMax, rightMax));
  }
}

The solution is four lines of logic. Each line maps directly to one of the |H| hints in the Firecode problem:

• Base case: Return Integer.MIN_VALUE for null nodes
• Left recursion: int leftMax = maxData(root.left)
• Right recursion: int rightMax = maxData(root.right)
• Combine: Math.max(root.data, Math.max(leftMax, rightMax))

Handling a Larger Tree

Here's a more complex test case to see how the algorithm scales. The tree [1, 2, 3, #, #, 4, 5, 6, #, 8, #, 9, #, #, #, 11, #, 12] has the maximum buried deep in the tree:

The recursion visits all 10 nodes, and the maximum of 12 is found at the bottom-right of the left branch. No matter where the maximum hides, the algorithm will find it.

The All-Negative Edge Case

Consider this tree where every value is negative or zero:

The maximum is 0, sitting deep in the right subtree. This is where the Integer.MIN_VALUE base case pays off. If we had used 0 as our null sentinel, the algorithm would have returned 0 even without finding it in the tree. With MIN_VALUE, only actual node data can win the comparison.

Complexity Analysis

Time Complexity: O(n)

Every node is visited exactly once. At each node, we do a constant amount of work (two comparisons). Total work is proportional to the number of nodes.

Space Complexity: O(log n) average, O(n) worst case

The space comes from the recursive call stack. For a balanced binary tree with n nodes, the height is approximately log(n), so the stack holds at most O(log n) frames. For a completely skewed tree where every node has only one child, the height equals n, and the stack space degrades to O(n).

Alternative Approaches

1. Iterative BFS: Use a queue for level-order traversal, tracking the maximum as you go. O(n) time, O(n) space for the queue.
2. Iterative DFS: Use an explicit stack instead of the call stack. Same complexity but avoids stack overflow on very deep trees.

The recursive approach is the standard interview answer because it's clean, concise, and directly mirrors the tree's recursive structure.

Common Pitfalls

1. Wrong base case value: Returning 0 or -1 instead of Integer.MIN_VALUE breaks all-negative trees. This is the single most common mistake.

2. Forgetting the current node: Comparing only left and right maximums without including root.data:

   // Wrong - ignores the current node's value
   return Math.max(leftMax, rightMax);
   

3. Null pointer exception: Not checking for null before accessing root.data:

   // Wrong - crashes on null input
   int leftMax = maxData(root.left);
   return Math.max(root.data, leftMax);  // What if root is null?
   

4. Assuming BST ordering: If you try to find the max by always going right, you'll get the wrong answer in a general binary tree.

Interview Tips

When solving this in an interview:

1. Clarify the tree type: "Is this a binary search tree or a general binary tree?" The approach differs significantly.

2. State the base case explicitly: "For null nodes, I'll return Integer.MIN_VALUE so it never affects comparisons." This shows you've thought about edge cases upfront.

3. Trace through a small example: Draw a 3-node tree and show how values propagate up from leaves to root.

4. Mention the space complexity: Many candidates forget that recursion uses stack space. Pointing this out demonstrates solid understanding.

5. Know the follow-ups:

   • "How would you find the max in a BST?" (Just follow right children, O(h) time)
   • "How would you find the second largest?" (Track top two values during traversal)
   • "What about the maximum path sum?" (Similar recursion, harder to combine)

Key Takeaways

• The recursive formula max(node.data, maxData(left), maxData(right)) with Integer.MIN_VALUE as the null base case solves this in O(n) time.
• Returning Integer.MIN_VALUE for null nodes is essential for correctness with negative values. This detail separates a correct solution from a subtly broken one.
• This "solve left, solve right, combine" pattern is the foundation of most binary tree recursion problems, from height to diameter to path sums.
• Space complexity depends on tree shape: O(log n) for balanced trees, O(n) for skewed trees.
• Always trace through an all-negative example when testing. It catches the most common base case mistake.

Practice Makes Perfect

Once you're comfortable finding the maximum node, try these related problems to reinforce the pattern:

• Find the height of a binary tree (same structure, different combine step)
• Check if a binary tree is balanced
• Find the maximum path sum in a binary tree (harder variant)
• Find the minimum depth of a binary tree

This problem and thousands more are available on Firecode, where over 50,000 engineers have prepared for technical interviews. Whether you're just starting with trees or looking to sharpen your recursive thinking, consistent practice is what gets you there.

Solutions in Other Languages

Python

import sys

class Solution:
    def max_data(self, root):
        if root is None:
            return -sys.maxsize - 1

        left_max = self.max_data(root.left)
        right_max = self.max_data(root.right)

        return max(root.data, left_max, right_max)

Python's built-in max function accepts multiple arguments, so the combine step is a single call.

JavaScript

class Solution {
  maxData(root) {
    if (root === null) {
      return Number.NEGATIVE_INFINITY;
    }

    const leftMax = this.maxData(root.left);
    const rightMax = this.maxData(root.right);

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

Like Python, Math.max in JavaScript accepts multiple arguments.

TypeScript

class Solution {
  maxData(root: TreeNode | null): number {
    if (root === null) {
      return Number.NEGATIVE_INFINITY;
    }

    const leftMax = this.maxData(root.left);
    const rightMax = this.maxData(root.right);

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

C++

#include <climits>
#include <algorithm>

class Solution {
public:
  int maxData(TreeNode *root) {
    if (root == nullptr)
      return INT_MIN;

    int leftMax = maxData(root->left);
    int rightMax = maxData(root->right);

    return std::max(root->data, std::max(leftMax, rightMax));
  }
};

C++ uses INT_MIN from <climits> and std::max from <algorithm>.

Go

import "math"

func (s *Solution) MaxData(root *TreeNode) int {
    if root == nil {
        return math.MinInt
    }

    leftMax := s.MaxData(root.Left)
    rightMax := s.MaxData(root.Right)

    if root.Data > leftMax && root.Data > rightMax {
        return root.Data
    }
    if leftMax > rightMax {
        return leftMax
    }
    return rightMax
}

Go does not have a generic max function in older versions, so we use manual comparisons.

Scala

class Solution {
  def maxData(root: TreeNode): Int = {
    if (root == null) return Int.MinValue

    val leftMax = maxData(root.left)
    val rightMax = maxData(root.right)

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

Kotlin

class Solution {
  fun maxData(root: TreeNode?): Int {
    if (root == null) return Int.MIN_VALUE

    val leftMax = maxData(root.left)
    val rightMax = maxData(root.right)

    return maxOf(root.data, leftMax, rightMax)
  }
}

Kotlin's maxOf accepts varargs, making the combine step clean.

Ruby

class Solution
  def max_data(root)
    return -Float::INFINITY if root.nil?

    left_max = max_data(root.left)
    right_max = max_data(root.right)

    [root.data, left_max, right_max].max
  end
end

Ruby's array max method provides a concise way to find the largest of three values.

Swift

class Solution {
    func maxData(_ root: TreeNode?) -> Int {
        if root == nil {
            return Int.min
        }

        let leftMax = maxData(root!.left)
        let rightMax = maxData(root!.right)

        return max(root!.data, max(leftMax, rightMax))
    }
}

Rust

impl Solution {
    pub fn max_data(&self, root: Option<Box<TreeNode>>) -> i32 {
        if root.is_none() {
            return i32::MIN;
        }
        let node = root.unwrap();

        let left_max = self.max_data(node.left);
        let right_max = self.max_data(node.right);

        node.data.max(left_max).max(right_max)
    }
}

Rust's method chaining on i32::max keeps the combine step readable.

C#

public class Solution {
    public int maxData(TreeNode? root) {
        if (root == null) return int.MinValue;

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

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

Dart

import 'dart:math';

class Solution {
  int maxData(TreeNode? root) {
    if (root == null) return -1 << 62;

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

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

Dart uses -1 << 62 as a large negative sentinel since it lacks an int.min constant for arbitrary-precision integers.

PHP

class Solution {
    public function maxData(?TreeNode $root): int {
        if ($root === null) {
            return PHP_INT_MIN;
        }

        $leftMax = $this->maxData($root->left);
        $rightMax = $this->maxData($root->right);

        return max($root->data, $leftMax, $rightMax);
    }
}

PHP's max function accepts multiple arguments, similar to Python.