# Article Attempt

• #### 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) {
}

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)
);
}
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.