Binary Tree Maximum Path Sum

Problem: Given a non-empty binary tree, find the maximum path sum. 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.

Approach: For each node there can be four ways that the max path goes through the node:

1. Node only
2. Max path through Left Child + Node
3. Max path through Right Child + Node
4. Max path through Left Child + Node + Right Child

The idea is to keep track of four paths and pick up the max one in the end. An important thing to note is, root of every subtree need to return maximum path sum such that at most one child of root is involved.

Implementation in C#:

        public int MaxPathSum()

        {

            if (this.Root == null)

            {

                return 0;

            }

            int maxSum = int.MinValue;

            this.MaxPathSum(this.Root, ref maxSum);

            return maxSum;

        }

        private int MaxPathSum(BinaryTreeNode node, ref int maxSum)

        {

            if (node == null)

            {

                return 0;

            }

            int l = this.MaxPathSum(node.LeftNode, ref maxSum);

            int r = this.MaxPathSum(node.RightNode, ref maxSum);

            int maxWithSingleChild = Math.Max(Math.Max(l, r) + node.Value, node.Value);

            int maxSumOnNode = Math.Max(maxWithSingleChild, l + r + node.Value);

            maxSum = Math.Max(maxSum, maxSumOnNode);

            return maxWithSingleChild;

        }

Complexity: O(n)