Katkat
Back

Find the Maximum Value in a Binary Tree Recursively

Akuna CapitalSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Implement a recursive binary tree traversal to find the maximum integer value in a tree, with careful handling of pointer safety, sentinel values, and edge cases like all-negative nodes.

Problem Statement

Given the root of a binary tree, write a recursive function to find and return the maximum value stored across all nodes in the tree.

Your implementation should follow the standard binary tree definition:

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

Function Signature

int findMax(TreeNode* root);

Requirements & Edge Cases

  • If root is nullptr, the function should return INT_MIN (std::numeric_limits::min()).
  • The tree may contain negative values, including trees where every node has a negative value.
  • The tree is not necessarily a binary search tree (BST); values can appear in any order.
  • Consider the ambiguity of using INT_MIN as both an empty-tree sentinel and a potentially valid node value.

Constraints

  • The number of nodes in the tree is in the range [0, 10^5].
  • Node values are within standard 32-bit signed integer limits: -2^31 <= Node.val <= 2^31 - 1.
  • The tree height can be up to N in skewed cases.

Examples

Example 1

Input:
        1
       / \
      3   2
     /   / \
    5   4   7

Output: 7
Explanation: The nodes contain {1, 3, 2, 5, 4, 7}. The maximum value is 7.

Example 2

Input:
       -10
       /  \
     -20  -3

Output: -3
Explanation: All values are negative. The maximum value among {-10, -20, -3} is -3.

Example 3

Input: nullptr
Output: -2147483648 (INT_MIN)
Explanation: For an empty tree, return INT_MIN.

Hints

Hint 1

A node's maximum value in its subtree is the maximum among its own value, the maximum of its left subtree, and the maximum of its right subtree.

Hint 2

Using INT_MIN as a base case return for nullptr works well with std::max, but verify what happens if all node values are less than or equal to INT_MIN.

Hint 3

Recall that an unbalanced tree of size N can consume O(N) stack frames, so each recursive call must strictly perform O(1) auxiliary work.

Follow-up questions

  • How would you redesign the API to avoid ambiguity if a valid non-empty tree consists of a single node with value INT_MIN (e.g., using std::optional or exceptions)?
  • How can you convert this traversal into an iterative approach using an explicit stack to prevent stack overflow on deeply skewed trees?
  • If the binary tree were guaranteed to be a Binary Search Tree (BST), how does the time complexity change, and what would the traversal look like?