Find the Maximum Value in a Binary Tree Recursively
Company: Akuna Capital
Role: Software Engineer
Category: Software Engineering Fundamentals
Difficulty: medium
Interview Round: Technical Screen
# Find the Maximum Value in a Binary Tree Recursively
Given the following C++ binary-tree node shape, implement and explain a recursive depth-first function that returns the maximum value in the tree:
```cpp
struct TreeNode {
int value;
TreeNode* left;
TreeNode* right;
};
```
Use the source's recursive contract: a call on `nullptr` returns `INT_MIN`, so a missing child does not override a real negative value. For a nonempty root, return the greatest stored integer. Explain what the sentinel means if the public caller itself supplies an empty tree.
Your reasoning must cover both child pointers, negative-only trees, pointer safety, the recursive invariant, time and auxiliary-space complexity, and the risk of stack exhaustion in a highly skewed tree.
### Clarifying Questions to Ask
- Is the top-level tree guaranteed to be nonempty, or is `INT_MIN` also the public empty-tree result?
- Are node values any signed `int`, including `INT_MIN` itself?
- Must the implementation be recursive, or may production code use an explicit stack for deep trees?
- Is the function read-only, and can the input contain shared nodes or cycles?
### What a Strong Answer Covers
- A `nullptr` base case that returns `INT_MIN`.
- Recursive evaluation of both the left and right subtrees.
- A three-way maximum over the current value and both recursive results.
- Correct behavior when every stored value is negative, including `INT_MIN`.
- A subtree invariant, an induction argument, O(n) time, and O(h) call-stack space.
- An explicit tree-shape assumption and a plan for excessive recursion depth.
### Follow-up Questions
- Why would returning zero for a missing child fail on an all-negative tree?
- How would you write an iterative version without changing the result?
- How should the API distinguish an empty tree from a one-node tree whose value is `INT_MIN`?
Overview: Implement a recursive C++ traversal that returns the maximum value stored in a TreeNode binary tree. The solution preserves the reported null-pointer and `INT_MIN` behavior, handles negative-only trees, proves the subtree invariant, and analyzes linear work, call-stack depth, and empty-tree ambiguity.
Read the full Akuna Capital Software Engineer interview experience this question came from