Stack Bash - Master data structures and algorithms

Maximum Path Sum in a Binary Tree

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.
Binary Tree path with maximum sum
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.
Binary tree path examples
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


9 Essential Trees & Graphs Coding Interview Problems

Master Trees & Graphs by trying the coding challenges below.
  1. 1.Inorder TraversalEasy
  2. 2.Tree SumEasy
  3. 3.Tree HeightEasy
  4. 4.LCAMedium
  5. 5.Max Path SumHard
  6. 6.Search mazeMedium
  7. 7.Number of islandsMedium
  8. 8.Kth SmallestMedium
  9. 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.