Binary Tree Maximum Path Sum — Hard Coding Interview Question

A path in a binary tree is a sequence of nodes connected by edges, with no node repeated. Given the root of a binary tree, return the maximum path sum of any non-empty path (it need not pass through the root).

Example

Input: root = [1,2,3]

Output: 6

Constraints

• The number of nodes is in the range [1, 3 × 10⁴]
• -1000 ≤ Node.val ≤ 1000

Topics & Companies

Topics: trees

Asked by: Amazon, Meta, Microsoft, Google, Bloomberg

Optimal Solution Complexity

Time complexity: O(n). Space complexity: O(h).

Practice more

• All DSA Problems
• DSA Patterns