Search⌘ K
Home
Courses
Decode the Coding Interview in Go: Real-World Examples

Binary Tree Maximum Path Sum

Explore how to determine the maximum path sum in a binary tree, understanding the use of recursive functions to evaluate node contributions and handle cases where paths may exclude the root. This lesson helps you develop problem-solving skills for tree-based coding interview challenges.

We'll cover the following...

Description

A path in a binary tree is defined as:

A sequence of nodes such that each pair of adjacent nodes must have an edge connecting them. A node can only be included in a path at most once. Moreover, including the root in the path is not compulsory.

The path sum can be calculated by adding up all nodes’ values in the path. To solve this problem, we will calculate the maximum path sum given the root of a binary tree so that there won’t be any greater path than it in the tree.

Example

Let’s discuss the example below:

Coding exercise

Go (1.6.2)
package main
import (
  "fmt"
  "strconv"
  "encoding/json"
)
type TreeNode struct{
    val int
    left *TreeNode
    right *TreeNode
}
func maxPathSum(root *TreeNode) int {
    // write your code here
    return -1;
}
Binary Tree Maximum Path Sum

Solution

We’ll start by simplifying the problem and looking at the implementation of the maxContrib(node) function which takes a node as an argument and computes a maximum contribution that this node and one or none of its subtrees can add.

For example:

Now, if we are sure that the root is also included in the maximum path, the problem can be solved using maxContrib(root), and ...