Maximum Path Sum in a Binary Tree

Hard

A path in a binary tree can start and end at any two nodes in the tree that are connected via a set of edges.

Given the root node of a binary tree that contains nodes with numbers, write a function that returns the maximum sum of any path in the tree.

For example, if your function is given the following binary tree, the maximum path sum is 31.

The maximum sum can be found from the path between node 7 and node 8: 9 + 6 + 7 + 1 + 8 = 31.

Examples of Binary Tree Paths

Think of a path as a single line that can be drawn from one node to another, without needing to draw over any edge more than once.

The following is an example of a valid path in a binary tree.

Assume that every node in the tree has access to its left and right child nodes, and no access to the parent node.

Try it

class BinaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def max_path_sum(tree: BinaryTreeNode) -> int:
    # implement max_path_sum
    return 0

1class BinaryTreeNode:
2    def __init__(self, data):
3        self.data = data
4        self.left = None
5        self.right = None
6
7def max_path_sum(tree: BinaryTreeNode) -> int:
8    # implement max_path_sum
9    return 0

Solution

9 Essential Trees & Graphs Coding Interview Problems

Master Trees & Graphs by trying the coding challenges below.

1.Inorder TraversalEasy
2.Tree SumEasy
3.Tree HeightEasy
4.LCAMedium
5.Max Path SumHard
6.Search mazeMedium
7.Number of islandsMedium
8.Kth SmallestMedium
9.Sort K ArraysHard

Want to confidently pass your next coding interview?

Stack Bash helps new and veteran software engineers master data structures and algorithms for technical interviews.