Maximum Path Sum

You are given a non-empty binary tree, you need to return the maximum path sum. A path, in this problem, is defined as a sequence of nodes from any starting node to any other node in the tree alongwith the parent-child connections. Note that the path must contain at least one node and not necessarily needs to go through the root.

In the above tree, the path with the maximum sum is
7 -> 6 -> 3 -> 8 -> 10 -> 14 -> 13 with the sum 61.

Algorithm

We do a simple DFS traversal of the tree. For each node, there can be four ways that the maximum path goes through that particular node in the tree.

  1. Considering that particular node only.
  2. Maximum path through left child + Node’s value
  3. Maximum path through right child + Node’s value
  4. Maximum path through left child + Maximum path through right child + Node’s value.

The main idea is to keep track of all the four paths mentioned above and then choose the maximum one in the end. Also, it is important to note that the root of every subtree needs to return the max path sum such that at most one child of the root is involved.

In the below code,

  1. Variables l and r stores the maximum path sum going through the left and right child of the root.
  2. Variable maximum_with_one stores the maximum path for the parent call of root and this path must include at-most one child of the root.
  3. Variable maximum_top contains the sum when the node which is under consideration is the root of the path and no ancestors are considered.
  4. variable res stores the final answer which is the maximum of all the 4 paths.

For a clearer understanding, take a look at the code –

#include <bits/stdc++.h>

using namespace std;

struct Node{
  Node* left;
  Node* right;
  int data;
};

Node* createNode(int key){
    Node* temp = new Node();
    temp->data = key;
    temp->right = nullptr;
    temp->left = nullptr;
    return temp;
}

Node* root = nullptr;

Node* insertNode(Node* node, int key){
    Node* temp = createNode(key);
    if(root == nullptr){
        root = temp;
        return root;
    }
    if(node == nullptr){
        return temp;   
    }
    
    if(key < node->data){
        node->left = insertNode(node->left, key);
    }else if(key > node->data){
        node->right = insertNode(node->right, key);
    }
    return node;
}

void levelOrderTraversal(){
    Node* temp = root;
    queue<Node*> q;
    q.push(temp);
    while(!q.empty()){
        Node* front = q.front();
        cout<<front->data<<" ";
        q.pop();
        if(front->left != nullptr){
            q.push(front->left);
        }
        if(front->right != nullptr){
            q.push(front->right);
        }
    }
}

int dfs(Node* root, int &ans)
{
    if(root == nullptr){
    	return 0;
    }

    int l = dfs(root->left, ans);
    int r = dfs(root->right, ans);
    int maximum_with_one = max(max(l, r) + root->data, root->data);
    int maximum_top = max(maximum_with_one, l + r + root->data);      
    ans = max(ans, maximum_top);
    return maximum_with_one;
}

int maxPathSum(Node* root) {
    int ans = INT_MIN;
    dfs(root,ans);
    return ans;
}

int main()
{
    insertNode(root, 8);
    insertNode(root, 3);
    insertNode(root, 10);
    insertNode(root, 1);
    insertNode(root, 6);
    insertNode(root, 14);
    insertNode(root, 4);
    insertNode(root, 7);
    insertNode(root, 13);
    levelOrderTraversal();
    cout<<endl;
    cout<<"The maximum path sum is : "<<maxPathSum(root);
    return 0;
}

Also, take a look at another popular interview problem Spiral Order Traversal.

One comment

Leave a Reply

Your email address will not be published.