#### Approach #1 Depth-First Search [Accepted]

**Intuition**

We will modify DFS algorithm to return the pair of integer values.

- First value of this pair is an '
**ark**' value - best sum that*won't use*current node. - Second value is best sum that
*will*use current node - the '**continue**' value.

When we get pair for the root node, we'll just pick larger of the 2 values.

So now we need to find a way to create this pair for every node in the tree. This way we will traverse the tree only once.

Let's consider '**continue**' part of the pair. It is the largest number from the 3 values:

- Just current node
- Current node + Current node's left son 'continue' part
- Current node + Current node's right son 'continue' part

The '**ark**' part is the largest number from the next 6 values:

- Just current node
- Current node + Current node's left son 'continue' part
- Current node + Current node's right son 'continue' part
- Just current node's left son 'ark' part
- Just current node's right son 'ark' part
- Current node + Current node's left son 'continue' part + Current node's right son 'continue' part

**Complexity Analysis**

Let ** n** be the number of nodes in the tree.

- Time complexity : $$O(n)$$.

We visit each node only once. All operations in one node take O(1) time (because arrays '**arks**' and '**continues**' have fixed size), so the overall time complexity is $$O(n) * O(1) = O(n)$$

**C++**

```
// long long prevents overflow errors
typedef long long ll;
class Solution {
public:
int maxPathSum(TreeNode* root) {
pair<ll, ll> answer = dfs(root);
return max<ll>(answer.first, answer.second);
}
private:
pair<ll, ll> dfs(TreeNode *root)
{
// if root is null, return very small number
if (!root)
return make_pair(-3e9, -3e9);
else
{
// 'ark', 'continue' for the left son
pair<ll, ll> left = dfs(root->left);
// 'ark', 'continue' for the right son
pair<ll, ll> right = dfs(root->right);
ll arks[] = {
left.first,
right.first,
left.second + right.second + (ll)(root->val),
left.second + root->val,
right.second + root->val,
(ll)root->val
};
ll continues[] = {
left.second + root->val,
right.second + root->val,
(ll)(root->val)
};
// return maximum values from 'arks' and 'continues' arrays
return make_pair(
*max_element(arks, arks+6),
*max_element(continues, continues+3)
);
}
}
};
```