Find the Maximum Root-to-Leaf Path Sum in a Binary Tree

Quick Overview

Find the maximum binary-tree root-to-leaf path sum with correct negative-value and single-child handling, a recurrence proof, and path reconstruction options.

Find the Maximum Root-to-Leaf Path Sum in a Binary Tree

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

Given a nonempty binary tree with numeric node values, return the greatest sum along a path that starts at the root and ends at a leaf. A leaf has no children. Negative values are allowed. ### Constraints & Assumptions The source says maximum root-to-leaf path without specifying whether maximum means node-value sum or path length. This practice exercise explicitly chooses numeric sum; confirm that interpretation. A longest-path-by-length task would use a different objective. ### Clarifying Questions to Ask - Does maximum mean the sum of node values or the number of nodes/edges? - Must the path end at a leaf, even if every continuation reduces the sum? - Should an empty tree return no result or raise an error? ```hint Missing children are not zero-cost exits A root-to-leaf path cannot stop early at an internal node merely to avoid negative descendants. ``` ### What a Strong Answer Covers - A recursive best suffix from each node to a leaf. - Distinguishing a missing child from a valid zero-sum path. - Single-child nodes, all-negative trees, and stack depth. ### Follow-up Questions - How would you return the actual path as well as its sum? - Why would a leaf-to-leaf maximum require different state?

Overview: Find the maximum binary-tree root-to-leaf path sum with correct negative-value and single-child handling, a recurrence proof, and path reconstruction options.

Read the full Amazon Software Engineer interview experience this question came from

Amazon logo
Amazon
Nov 10, 2026
hardSoftware EngineerOnsiteCoding & Algorithms
0
0

Given a nonempty binary tree with numeric node values, return the greatest sum along a path that starts at the root and ends at a leaf. A leaf has no children. Negative values are allowed.

Constraints & Assumptions

The source says maximum root-to-leaf path without specifying whether maximum means node-value sum or path length. This practice exercise explicitly chooses numeric sum; confirm that interpretation. A longest-path-by-length task would use a different objective.

Clarifying Questions to Ask Guidance

  • Does maximum mean the sum of node values or the number of nodes/edges?
  • Must the path end at a leaf, even if every continuation reduces the sum?
  • Should an empty tree return no result or raise an error?

What a Strong Answer Covers Guidance

  • A recursive best suffix from each node to a leaf.
  • Distinguishing a missing child from a valid zero-sum path.
  • Single-child nodes, all-negative trees, and stack depth.

Follow-up Questions Guidance

  • How would you return the actual path as well as its sum?
  • Why would a leaf-to-leaf maximum require different state?