Binary Tree Maximum Path Sum

To solve the Binary Tree Maximum Path Sum problem, I would first clarify that a path must be non-empty and can start and end at any node. My approach uses a depth-first search with a helper function. This function returns the maximum path sum starting from the current node and going down either the left or right child, but not both. Why? Because a valid path cannot split into two branches; however, when evaluating the current node, we consider the scenario where the path turns at this node, combining the left and right branches to form a potential new maximum. I would initialize a global variable to track the highest sum found so far. In each recursive step, I calculate the max gain from the left and right children. If a child's contribution is negative, I treat it as zero because including it would reduce the total sum. Then, I update the global maximum with the sum of the current node plus both left and right gains. Finally, I return the current node value plus the maximum of the left or right gain to the parent caller. This ensures we explore all possible turning points in the tree. For example, if the tree has a root of -10 with left child 9 and right child 20 containing 15 and 7, the algorithm correctly identifies the path 15-20-7 as the maximum. This solution runs in O(N) time since we visit each node once, and uses O(H) space for the recursion stack, which fits Meta's performance expectations.