# LeetCode 124: Binary Tree Maximum Path Sum

I'm posting my code for a LeetCode problem. If you'd like to review, please do so. Thank you for your time!

### Problem

Given a non-empty binary tree, find the maximum path sum.

For this problem, 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.

### Example 1:

Input: [1,2,3]

1
/ \
2   3

Output: 6


### Example 2:

Input: [-10,9,20,null,null,15,7]

-10
/ \
9  20
/  \
15   7

Output: 42


### Inputs

[1,2,3]
[-10,9,20,null,null,15,7]
[-10,9,20,null,null,15,7,9,20,null,null,15,7]
[-10,9,20,null,null,15,7,9,20,null,null,15,720,null,null,15,7,9,20,null,null,15,7]
[-10,9,20,null,null,15,7,9,20,null,null,15,720,null,null,15,7,9,20,null,null,15,7999999,20,null,null,15,7,9,20,null,null,15,720,null,null,15,7,9,20,null,null,15,7]


### Outputs

6
42
66
791
8001552


### Code

#include <cstdint>
#include <algorithm>

struct Solution {
int maxPathSum(TreeNode* root) {
std::int_fast64_t sum = INT_FAST64_MIN;
depthFirstSearch(root, sum);
return sum;
}

private:
static std::int_fast64_t depthFirstSearch(
const TreeNode* node,
std::int_fast64_t& sum
) {

if (!node) {
return 0;
}

const std::int_fast64_t left = std::max(
(std::int_fast64_t) 0,
depthFirstSearch(node->left, sum)
);
const std::int_fast64_t right = std::max(
(std::int_fast64_t) 0,
depthFirstSearch(node->right, sum)
);
sum = std::max(sum, left + right + node->val);
return std::max(left, right) + node->val;
}
};



### References

There's not much to say about your answer, it looks fine! One could quibble over the names of variables, maybe left and right could be named left_sum and right_sum for example, and you could've used auto for the type of those two variables. But other than that I think there is nothing that can be improved.

Not sure why you decided to use std::int_fast64_t over the common int that is used as the type of the tree nodes values.

But since you did, it would be more idiomatic to do at least:

static_cast<std::int_fast64_t>(0);


(std::int_fast64_t) 0;

• Maybe it is better to avoid casting altogether. Casting implies you started with some different type. You can construct a zero of the proper type directly by writing: std::int_fast64_t(0) – G. Sliepen Jul 23 '20 at 10:00
• Or create a named object static constexpr std::int_fast64_t fast_zero(0); – Martin York Jul 23 '20 at 18:44