Maximum Path Sum of Binary Tree Editorial

Practice Problem Link: Maximum Path Sum of Binary Tree

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

A path between two nodes p and q is defined as a sequence of nodes encountered while travelling from node p to node q (or vice-versa) via parent-child connections. The path does not need to pass through the root node. The sum of the values of all these nodes in the path is considered as the path sum.

A binary tree can have multiple paths depending on the number of nodes. Thus, the path with the maximum sum is considered the maximum path sum for the tree. Note that the path can be empty, i.e. contain no nodes.

Given the reference to the root node of a binary tree, return its maximum path sum.

Naive Approach

The idea is to calculate the maximum path sums starting from each node and return the maximum value among them. This can be done as:

• Traverse the given tree and for each node find the maximum path sum starting from that node and update the answer.
• Now, recursively repeat this step for the left and right child of the current node.

Analysis

• Time Complexity: O(n2)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/
void getPathSum(Node* root, int &pathSum, int currentSum) {
	if (root == NULL) {
		return;
	}
	pathSum = max(pathSum, currentSum + root->data);
	getPathSum(root->left, pathSum, currentSum + root->data);
	getPathSum(root->right, pathSum, currentSum + root->data);
}
int getMaxPathSum(Node* root, int &maximumPath) {
	if (root == NULL) {
		return 0;
	}
	int leftSum = 0;
	int rightSum = 0;
	getPathSum(root->left, leftSum, 0);
	getPathSum(root->right, rightSum, 0);
	maximumPath = max(maximumPath, leftSum + rightSum + root->data);
	getMaxPathSum(root->left, maximumPath);
	getMaxPathSum(root->right, maximumPath);
	return maximumPath;
}
int maxPathSum(Node *root) {
    int maximumPath = INT_MIN;
	getMaxPathSum(root, maximumPath);
	return maximumPath;
}

Java

class Solution {
	/* This is the Node class definition
	
	class Node {
		public Node left;
		public Node right;
		public int data;

		public Node(int data) {
			this.data = data;
		}
	}
	*/
	static int maximumPath, pathSum;
	void getPathSum(Node root, int currentSum) {
		if (root == null) {
			return;
		}
		pathSum = Math.max(pathSum, currentSum + root.data);
		getPathSum(root.left, currentSum + root.data);
		getPathSum(root.right, currentSum + root.data);
	}
	int getMaxPathSum(Node root) {
		if (root == null) {
			return 0;
		}
		pathSum = 0;
		getPathSum(root.left, 0);
		int leftSum = pathSum;
		pathSum = 0;
		getPathSum(root.right, 0);
		int rightSum = pathSum;
		maximumPath = Math.max(maximumPath, leftSum + rightSum + root.data);
		getMaxPathSum(root.left);
		getMaxPathSum(root.right);
		return maximumPath;
	}
	int maxPathSum(Node root) {
	    maximumPath = Integer.MIN_VALUE;
		getMaxPathSum(root);
		return maximumPath;
	}
}

Optimal Approach

A node can be part of the maximum path in four ways.

1. It is the only node in the path.
2. The maximum path through left child + node.
3. The maximum path through the right child + node.
4. The maximum path through the left child + node + maximum path through the right child.

Perform a postorder traversal and consider the above four cases for each node and update the answer.

Note: The recursive function should return the maximum path sum starting from that node such that at most one child of the node is considered in the path.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/
int getMaxPathSum(Node* root, int &maximumPath) {
	if (root == NULL) {
		return 0;
	}
	int leftSum = getMaxPathSum(root->left, maximumPath);
	int rightSum = getMaxPathSum(root->right, maximumPath);
	int maxPathWithOneChild = max(root->data, max(leftSum, rightSum) + root->data);
	maximumPath = max(maximumPath, max(maxPathWithOneChild, leftSum + rightSum + root->data));
	return maxPathWithOneChild;
}
int maxPathSum(Node *root) {
    int maximumPath = INT_MIN;
	getMaxPathSum(root, maximumPath);
	return maximumPath;
}

Java

class Solution {
	/* This is the Node class definition
	
	class Node {
		public Node left;
		public Node right;
		public int data;

		public Node(int data) {
			this.data = data;
		}
	}
	*/
	static int maximumPath;
	int getMaxPathSum(Node root) {
		if (root == null) {
			return 0;
		}
		int leftSum = getMaxPathSum(root.left);
		int rightSum = getMaxPathSum(root.right);
		int maxPathWithOneChild = Math.max(root.data, Math.max(leftSum, rightSum) + root.data);
		maximumPath = Math.max(maximumPath, Math.max(maxPathWithOneChild, leftSum + rightSum + root.data));
		return maxPathWithOneChild;
	}
	int maxPathSum(Node root) {
	    maximumPath = Integer.MIN_VALUE;
		getMaxPathSum(root);
		return maximumPath;
	}
}