Algorithm {Binary Tree Maximum Path Sum}

I’ve just solved one more problem from leetcode and going to share that solution. So, solved problem calls Binary Tree Maximum Path Sum.

Problem description:

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

Return 6.

OK, stop and think …. What do we have ???  The main point is binary tree. We can use perfect traversing algorithms. In our case we need to use post order traversal, is not it ? OK, good, if we got left, right and current what we should check ???
We should understand how post order is working . Tree should be like that:

We will traverse to the left, check if node is null return (the max path equals to ) and go to the right node, again if node is null return and go up to parent. Parent is 2. We should check what is the max path left +parent or right +parent. After that check if this max path biggest that current value (because left or right can be negative).

Good, after that we will have max current path in other words max path for current value. So, after that we should check what is the bigger max current path or full path (full path is left + current + right, because the path can start and end at any node) and if that value biggest that stored set it like a max path. That is all, so, words are good but better code, let’s go …

So, that is all, if you have some questions don’t hesitate to ask me 🙂
Cheers !!!

READ  Algorithm {Triangle}

Leave a Reply

Your email address will not be published. Required fields are marked *