• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

LeetCode: Binary Tree Maximum Path Sum

October 5, 2019 by Arshdeep Singh

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

Input: [1,2,3]

        1
      /    \
    2      3

Output: 6

Example 2:

Input: [-10,9,20,null,null,15,7]

         -10
         /    \
       9     20
             /    \
          15    7

Output: 42

Question Link: Binary Tree Maximum Path Sum 

Solution: 

On the first look, the problems looks like a All pairs shortest path problem. That can be solved using Floyd-Warshall algorithm which is used to find shortest distance between all the points of the graph/tree. But then complexity would be O(n^3) which is not optimal for the problem.

Further thinking reveals that we can apply Post Order Tree Traversal along with Dynamic Programming to solve this problem.

The main observation for the dp states in this problem is that there can be four ways the current node can be a part of the maximum path:

  1. The Node is itself the only node in maximum path.case 1
  2. Node along with maximum path with the left childcase 2
  3. Node along with maximum path with the right childcase 3
  4. The Node along with maximum path with the left child as well as the right child

case 4

We have to check the maximum of the above four and update our answer accordingly.

So now as we know the states we have to look for the current node, what is left is to ask what we should pass above to the parent?

We obviously can’t pass the 4th one above as the cureent node is not a terminal node of the maximum path but a intermediate one. So the idea is to pass the maximum of the rest of the three above and proceed in the similar manner. After the passing each result, the tree would look something like this:

passes

Implementation details can be understood in the code:

Code:

Implemented in C++

 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxx; //stores the result
   //Post Order Traversal Helper Function
    int postOrder(TreeNode* root) {
        if(root==NULL) return 0; //base condition
        int left = max(0, postOrder(root ->  ;left)); //takes the maximum from left child and 0
        int right = max(0, postOrder(root - >;right)); //takes the maximum from right child and 0
        maxx = max(maxx, left + right + root->val); //calculates thg maximum possible at the current node (this comprises all four cases 1,2,3 and 4)
        return max(left, right) + root->val; //returning maximum from left, right along with current.
    }

    int maxPathSum(TreeNode* root) {
        maxx=root->val; //initializing with root's value
        postOrder(root); //traversing using Post Order Traversal
        return maxx; //returning maximum
    }
};

Similar Articles

Filed Under: Amazon Interview Question, Data Structure, Flipkart Interview Questions, Google, LeetCode, Microsoft Interview Questions Tagged With: Binary Tree, tree

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Find next greater number with same set of digits

Generate largest number arranging a no. of given non negative integer numbers

Word Break Problem

Coin Collection Dynamic Programming

Inorder and Preorder traversals of a Binary Tree given. Output the Postorder traversal of it.

Maximum sum contiguous subarray of an Array

Python Dictionaries

SAP Off Campus Hiring_ March 2015 Verbal Skills

Find the element that appears once others appears thrice

BlueStone E-commerce Interview Experience

‘N’ Story Building, with 1,2,3 steps how many ways can a person reach top of building.

Mirror of Tree

Count number of ways to reach a given score in a game

Python Array String

Fibonacci Hashing & Fastest Hashtable

robot standing at first cell of an M*N matrix. It can move only in two directions, right and down. In how many ways, it can reach to the last cell i.e. (M, N) Code it

Test Cases for Round Function

Apriori algorithm C Code Data Mining

Check Binary Tree is Binary Search Tree or not

1014 Practice Question of New GRE – Princeton

Amazon Interview On-Campus For Internship – 1

Hackerearth : Counting Subarrays

Leetcode: Edit Distance

Generate next palindrome number

Find position of the only set bit

Reverse a Linked List in groups of given size

C++ OOPs Part1

Facebook Interview Question : Interleave List

Maximum of all subarrays of size k

Templates in C++

Copyright © 2025 · Genesis Framework · WordPress · Log in