Maximum Path Sum in Binary Tree

Problem:

Given a binary tree as an input, we want to find the maximum path sum.

We define path to be a sequence of nodes from some start node to any other node in the tree along parent and child connections. Path has to contain at least a single node, and does not have to go through the root.

Examples:

					
#Given the below binary tree
       1
      / \
     2   3
   /   \
  4     5
				

Return 11. (The Path is 4 , 2 and 5 and does not go through the root)

However, since we are using “2” as the bridge where the path goes through, we cannot include 1, if we wanted to include “1” then we would have to drop either the left or right branch of “2”.

Paths may be more complex.

Hints and Answer Checklist