# Maximum Path Sum in a Binary Tree

HardA

**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

## 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