Binary Tree Maximum Path Sum

Binary Tree Maximum Path Sum is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Recursive Postorder Traversal subpattern.

Problem statement

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

Example 1:

Input: root = [1,2,3] Output: 6 Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

Example 2:

Input: root = [-10,9,20,null,null,15,7] Output: 42 Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

Constraints:

- The number of nodes in the tree is in the range [1, 3 104].

- -1000 <= Node.val <= 1000

Topics and companies

Topics: Dynamic Programming, Tree, Depth-First Search, Binary Tree.

Reported in interviews at Facebook, Amazon, Google, Microsoft, Bloomberg, Oracle, Adobe, Apple, Yahoo, ByteDance.

How to practise Binary Tree Maximum Path Sum on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(h) space.

Open Binary Tree Maximum Path Sum in the code editor, or read the Binary Tree Maximum Path Sum editorial for a worked solution with its approach and complexity analysis.

Where Binary Tree Maximum Path Sum sits in the DSA pattern sheet

Problems related to Binary Tree Maximum Path Sum

Other problems that use the same Recursive Postorder Traversal and Tree Traversal Patterns (DFS & BFS) techniques:

Preparing this workspace.