LeetCode 124: Binary Tree Maximum Path Sum

When solving for the maximum path sum of a binary tree, use DFS traversal approach and consider the maximum sum that can be achieved by traversing each node’s left and right subtrees. Each node can form a unique path that includes itself, as well as its left and right subtrees. Additionally, it can also be a part of the path formed by its parent node. To ensure the maximum path sum, negative values of left or right nodes should not be included in the calculations.

summary card

Table of Contents

· Problem
· Approach
· Graphical Explanation
· Code Implementation
  ∘ Complexity
  ∘ Golang
  ∘ Python

Problem

124. Binary Tree Maximum Path Sum

The path sum of a path is the sum of the node’s values in the path. Note that the path does not need to pass through the root.

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

• -1000 <= Node.val <= 1000 ( the value of a node in the binary tree can be negative)

example

Input: root = [-10,9,20,null,null,15,7]
Output: 42

Approach

When determining the maximum path sum in a binary tree, it is important to consider that each node can form a distinct path composed of itself and its left and right subtrees, as well as being a part of a path formed by its parent node. When calculating the path sum, negative values of left or right nodes should be disregarded to maintain the maximum sum possible.

• A path composed of a node and its left and right subtrees

possible maximum path sum = node + max(left, 0) + max(right, 0)

• Being a part of a path formed by a node’s parent node

maximum path sum of subtree = node + max(left, right, 0)

two different calculations for each node

Perform a depth-first search (DFS) of the tree and at each node, calculate the maximum sum that can be obtained by traversing the left and right subtrees.

Graphical Explanation

process

Code Implementation

Complexity

Time: O(n)
Space: O(h)
n: the total number of nodes in the binary tree
h: the height of the binary tree

Golang

Python

You can access the source code here.

LeetCode Problem

• 124. Binary Tree Maximum Path Sum