Binary Tree Maximum Path Sum, non-recursive, Time Limit Exceeded

Question

I'm struggling with this problem, which I want to solve in non-recursive way. There seems no logic error in my algorithm, 73% test cases passed. But it can't handle the big data, reported "Time Limit Exceeded". I appreciate if somebody could give me some hint how to do it in non-recursive and avoid time limit exceed, thanks in advance!

Problem Link

I believe there's also a similar one in LeetCode.

http://www.lintcode.com/en/problem/binary-tree-maximum-path-sum-ii/

Problem description:

Given a binary tree, find the maximum path sum from root. The path may end at any node in the tree and contain at least one node in it.

Example:

Given the below binary tree:

1

/ \

2 3

return 4. (1->3)

Judge

Time Limit Exceeded

Total Runtime: 1030 ms

Input Input Data

{-790,-726,970,696,-266,-545,830,-866,669,-488,-122,260,116,521,-866,-480,-573,-926,88,733,#,#,483,-935,-285,-258,892,180,279,-935,675,2,596,5,50,830,-607,-212,663,25,-840,#,#,-333,754,#,817,842,-220,-269,9,-862,-78,-473,643,536,-142,773,485,262,360,702,-661,244,-96,#,519,566,-893,-599,126,-314,160,358,159,#,#,-237,-522,-327,310,-506,462,-705,868,-782,300,-945,-3,139,-193,-205,-92,795,-99,-983,-658,-114,-706,987,292,#,234,-406,-993,-863,859,875,383,-729,-748,-258,329,431,-188,-375,-696,-856,825,-154,-398,-917,-70,105,819,-264,993,207,21,-102,50,569,-824,-604,895,-564,-361,110,-965,-11,557,#,202,213,-141,759,214,207,135,329,15,#,#,244,#,334,628,509,627,-737,-33,-339,-985,349,267,-505,-527,882,-352,-357,-630,782,-215,-555,132,-835,-421,751,0,-792,-575,-615,-690,718,248,882,-606,-53,157,750,862,#,940,160,47,-347,-101,-947,739,894,#,-658,-90,-277,-925,997,862,-481,-83,708,706,686,-542,485,517,-922,978,-464,-923,710,-691,168,-607,-888,-439,499,794,-601,435,-114,-337,422,#,-855,-859,163,-224,902,#,577,#,-386,272,-9 ...

Expected

6678

My Code C++

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param root the root of binary tree.
     * @return an integer
     */
    int maxPathSum2(TreeNode *root) {
        if (root == NULL) return 0;
        findLeaf(root);
        return global_max;
    }

private:
    int global_max = INT_MIN;

    void findLeaf(TreeNode* root) {
        unordered_map<TreeNode*, TreeNode*> parent;
        stack<TreeNode*> traverse;
        parent[root] = NULL;
        traverse.push(root);

        while(!traverse.empty()) {
            TreeNode* p = traverse.top();
            traverse.pop();
            if (!p->left && !p->right) {
                findPathMaxSum(p, parent);
            }
            if (p->right) {
                parent[p->right] = p;
                traverse.push(p->right);
            }
            if (p->left) {
                parent[p->left] = p;
                traverse.push(p->left);
            }
        }
    }

    void findPathMaxSum(TreeNode* leaf, unordered_map<TreeNode*, TreeNode*> parent) {
        TreeNode* current = leaf;
        stack<TreeNode*> stk;
        int path_max = INT_MIN;
        int path_sum = 0;

        while (current) {
            stk.push(current);
            current = parent[current];
        }

        while (!stk.empty()) {
            current = stk.top();
            stk.pop();
            path_sum += current->val;
            path_max = path_max > path_sum ? path_max : path_sum;
        }

        global_max = global_max > path_max ? global_max : path_max;
    }
};

SOLVED

I accept the advice by @Dave Galvin and it works! Here's the code:

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param root the root of binary tree.
     * @return an integer
     */
    int maxPathSum2(TreeNode *root) {
        if (root == NULL) return 0;
        int global_max = INT_MIN;
        stack<TreeNode*> traverse;
        traverse.push(root);
        while(!traverse.empty()) {
            TreeNode* p = traverse.top();
            global_max = global_max > p->val ? global_max : p->val;
            traverse.pop();
            if (p->right) {
                traverse.push(p->right);
                p->right->val += p->val;
            }
            if (p->left) {
                traverse.push(p->left);
                p->left->val += p->val;
            }
        }
        return global_max;
    }
};

Bouncy

Why it is have to be non-recursive? – Recombination

@sudomakeinstall2 I just want to try it in a non-recursive way .... – Bouncy

Can you provide the link to where the problem is from? – Oakum

@A.Sarid LintCode, LeetCode – Bouncy

@sudomakeinstall2: Recursion is problematic in the real world. It usually consumes unpredictable amounts of stack memory, which is generally fairly limited. As the old saying goes: The only problem with recursion is recursion. – Availability

@xman, your time complexity is not linear in tree size. – Spirit

@xman, I edited my solution to an O(n) complexity one. – Spirit

Answer 1

From the top down, update each node by adding its parent's value to it. Keep track of your max value and its position. Return that at the end. O(n).

E.g., if your binary tree is T=[-4,2,6,-5,2,1,5], then we update it as: [-4, 2-4=-2, 6-4=2, -2-5 = -7, -2+2=4, 2+3=3, 2+5=7]

Here the answer is 7, going -4, 6, 5.

Especial

Answer 2

I guess that the problem with your code is that when you are traversing your tree, in each node you are iterating to calculate the maximum path. This ends up with a complexity of O(n^2). You need to calculate the maximum path on the flow (while traversing the tree).

In the solution below I used the post-order iterative algorithm from here. Please forgive me that I used this one instead of yours.

The solution (O(n)) is simply to add a field max_path to each node, and when visiting the actual node take the maximum between left and right:

void postOrderTraversalIterative(BinaryTree *root) {
    if (!root) return;
    stack<BinaryTree*> s;
    s.push(root);
    BinaryTree *prev = NULL;
    while (!s.empty()) {
        BinaryTree *curr = s.top();
        if (!prev || prev->left == curr || prev->right == curr) {
            if (curr->left)
                s.push(curr->left);
            else if (curr->right)
                s.push(curr->right);
        } else if (curr->left == prev) {
            if (curr->right)
                s.push(curr->right);
        } else {
            //Visiting the node, calculate max for curr
            if (curr->left == NULL && curr->right==NULL)
                curr->max_path = curr->data;
            else if (curr->left == NULL)
                curr->max_path = curr->right->max_path + curr->data;
            else if (curr->right == NULL)
                curr->max_path = curr->left->max_path + curr->data;
            else //take max of left and right
                curr->max_path = max(curr->left->max_path, curr->right->max_path) + curr->data;
            s.pop();
        }
        prev = curr;
    }
}

Oakum

I think you're right, it's better to add a field and compare but not to change the real value of the node. Now time complexity is linear :) – Bouncy

Answer 3

EDITED:

you won't need findPathMaxSum function. I also changed the parent map. Now it stores 2 values:

1. pointer to parent
2. path sum from root to the current node.

Here is the code.

class Solution {
public:
    /**
     * @param root the root of binary tree.
     * @return an integer
     */
    int maxPathSum2(TreeNode *root) {
        if (root == NULL) return 0;
        findLeaf(root);
        return global_max;
    }

private:
    int global_max = INT_MIN;

    void findLeaf(TreeNode* root) {
        unordered_map<TreeNode*, std::pair<TreeNode*,int> > parent;
        stack<TreeNode*> traverse;
        parent[root] = make_pair(NULL,root->val);
        traverse.push(root);

        while(!traverse.empty()) {
            TreeNode* p = traverse.top();
            traverse.pop();
            if (!p->left && !p->right) {
                // findPathMaxSum(p, parent);
                global_max=std::max(global_max,parent[p].second);
            }
            if (p->right) {
                parent[p->right] = make_pair(p, (p->right->val) +parent[p].second) ;
                traverse.push(p->right);
            }
            if (p->left) {
                parent[p->left] = make_pair(p, (p->left->val) +parent[p].second) ;
                traverse.push(p->left);
            }
        }
    };

OLD:

You want to pass the map by reference not by value in findPathMaxSum.

void findPathMaxSum(TreeNode* leaf, unordered_map<TreeNode*, TreeNode*> parent)

change it to.

void findPathMaxSum(TreeNode* leaf, unordered_map<TreeNode*, TreeNode*>& parent)

It makes your time complexity O(n*n).

Its running complexity will become O(n*log n). Although it did not work out as your constraints are tighter. So I posted a O(n) solution above.

Spirit

No, it doesn't change anything... and pass by reference won't effect the time complexity. – Bouncy

please post the link to the problem. passing by reference always does the job generally. – Spirit

"passing by reference always does the job" - Blanket statements like these are easily invalidated, with a single counter example. Make sure your statements don't turn wrong when trying to simplify them. – Availability

I edit my post and add the problem link, and I also take your advice to pass by reference but still Time Limit Exceeded. – Bouncy

@IInspectable, I apologize for the statement. I will be careful with my words from the next time. Thanks – Spirit

@dd2 Thanks for your answer and help too :) but this answer can not be compiled, I've solved the problem, now it's AC. I edit my post and add my code. – Bouncy