Binary Tree Maximum Path Sum

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

Approach

DFS: get the max along the height of left subtree and right subtree (mls & mrs)

max path sum at a node is max_of(node_val, node_val + mls, node_val + mrs, node_val + mls + mrs)

We need to take the maximum of max path sum at all nodes in the tree.

fun maxPathSum(root: TreeNode?): Int {

    if (root == null) return 0
    var maxSum = Int.MIN_VALUE

    // returns the max of the left path & right path sum
    fun maxSumUtil(node: TreeNode?): Int {
        // if empty return 0
        if(node == null) return 0

        // if leaf return its value
        if(node.left == null && node.right == null) {
            maxSum = maxOf(maxSum, node.`val`)
            return node.`val`
        }

        // find the max path along the height of left and right subtree
        val mls = maxSumUtil(node.left)
        val mrs = maxSumUtil(node.right)

        val maxAtNode = maxOf(node.`val`, node.`val` + maxOf(mls, mrs))

        maxSum = maxOf(maxSum, maxAtNode,  node.`val` + mls + mrs )

        return maxAtNode
    }

    maxSumUtil(root)

    return maxSum

}