Facebook interview question: Print out the path which has the maximum path sum of a binary tree


  • 1

    It's a follow up of LC 124, the interviewer wants to print out the path which has the maximum path sum, anyone has any ideas?


  • 0
    M

    @younghobbits maybe we could first find the "root" of the maximum path sum, and compute the sums of the nodes in its subtrees. Then start from the "root" recover the maximum path.


  • 0

    @milu Emmm..I'm not sure I understand your solution, the "root" you mean is it the root which the maximum path passing through? Why do we need to compute the sums and how to recover the maximum path? I think maybe this can be solved by adding nodes in a vector during the traverse of finding max path, but I didn't figure out how to maintain the vectors..


  • 0
    M

    @younghobbits Yeah, the "root" is the root of the maixmum path sum.
    Suppose, we know the "root" of the maximum path sum. How do we recover the path?
    Starting from the "root", we check the left subtree (root->left) first, then print the current root->val, then check the right subtree.
    Now suppose we have computed all the sums of the nodes in the subtrees and stored these sums in the val member (the original values can be restored if needed). For the left subtree, if root->left->val <= 0, we could just return. Otherwise, we check the two children of root->left and choose the child with positive and larger sum. I have this ugly code below:

    class Solution {
        struct PathInfo {
            int maxpath = 0, path = 0; // maxpath is the max path, path is the max path starting from the current node, path is not negative
            // now try to print out the path with maximum path sum
            // record the LCA
            TreeNode *lca;
        };
        
        PathInfo helper(TreeNode *root) {
            if (!root)
                return {INT_MIN, 0, NULL};
            PathInfo ans;
            PathInfo leftret  = helper(root->left);
            PathInfo rightret = helper(root->right);
            ans.path = max(0, max(leftret.path, rightret.path) + root->val);
            ans.maxpath = max(leftret.path + rightret.path + root->val, max(leftret.maxpath, rightret.maxpath));
            if (leftret.path + rightret.path + root->val >= max(leftret.maxpath, rightret.maxpath)) {
                ans.lca = root;
            }
            else if (leftret.maxpath >= rightret.maxpath) {
                ans.lca = leftret.lca;
            }
            else {
                ans.lca = rightret.lca;
            }
            return ans;
        }
        
        void printhelper(TreeNode *node, bool isLeft) {
            if (!node || node->val <= 0)
                return;
            // recover the node->val and store it in 'val'
            int val = node->val;
            if (!node->left) {
                if (node->right && node->right->val > 0)
                    val -= node->right->val;
            }
            else if (!node->right) {
                if (node->left && node->left->val > 0)
                    val -= node->left->val;
            }
            else if (max(node->left->val, node->right->val) > 0)
                val -= max(node->left->val, node->right->val);
            // if it's on the right side of the "root" (of the maximum path sum), print 'val' first
            if (!isLeft)
                cout << val << ", ";
            // print the maximum of left and right path
            if (!node->left)
                printhelper(node->right, isLeft);
            else if (!node->right)
                printhelper(node->left, isLeft);
            else {
                if (node->left->val > node->right->val)
                    printhelper(node->left, isLeft);
                else
                    printhelper(node->right, isLeft);
            }
            if (isLeft)
                        cout << val << ", ";
            return;
        }
        
        void printPath(TreeNode *root) {
            printhelper(root->left, true);
            cout << root->val << ", ";
            printhelper(root->right, false);
        }
        
        int computesums(TreeNode *root) {
            if (!root)
                return 0;
            int leftsum = computesums(root->left);
            int rightsum = computesums(root->right);
            int tmp = max(leftsum, rightsum);
            if (tmp > 0) {
                root->val += tmp;
            }
            return root->val;
        }
        
    public:
        int maxPathSum(TreeNode* root) {
            // return helper(root).maxpath;
            PathInfo ans = helper(root);
            computesums(ans.lca->left); computesums(ans.lca->right);
            printPath(ans.lca);
            return ans.maxpath;
        }
    };
    

    Hope someone could come up with a better and cleaner solution.


  • 0

    @milu Hi milu, thanks for your code and explaining, I got the idea. However, I was thinking if we can name a struct to store the node's height and the current maximum path, then do a post order traversal, to update the current node's height and path information according to its left child and right child. Here is my code, I tried a several cases are good but I don't know if I left some corner cases..

    pathInfo printDiameter(TreeNode* root){
        if(!root) return pathInfo(0,0);
        pathInfo left = printDiameter(root->left);
        pathInfo right = printDiameter(root->right);  // post order traversal
        pathInfo cur(0,0);
        int leftHeight = max(left.curHeight,0);
        int rightHeight = max(right.curHeight,0);
        cur.curHeight = max(leftHeight,rightHeight)+root->val;
        if(cur.curHeight == left.curHeight+root->val) cur.heightList = left.heightList;
        else if(cur.curHeight == right.curHeight+root->val) cur.heightList = right.heightList;
        cur.heightList.push_back(root->val);    // it would directly reach here if leftHeight and rightHeight is 0
        cur.maxPath = max(max(left.maxPath,right.maxPath),leftHeight+rightHeight+root->val);
        if(cur.maxPath == left.maxPath){
            cur.pathList = left.pathList;
        }
        else if(cur.maxPath == right.maxPath){
            cur.pathList = right.pathList;
        }
        else {
            if(!leftHeight && !rightHeight)
                cur.pathList.push_back(root->val);
            else if(!leftHeight || !rightHeight){
                cur.pathList = leftHeight ? left.heightList : right.heightList;
                cur.pathList.push_back(root->val);
            }
            else{
                cur.pathList = left.heightList;
                cur.pathList.insert(cur.pathList.end(), right.heightList.begin(), right.heightList.end());
                cur.pathList.push_back(root->val);
            }
        }
        return cur;
    }
    

  • 0
    M

    @younghobbits Hi, I think the basic idea should work, but your code may fail if there are negative values in the tree.
    You may want to change to if (!root) return pathInfo(INT_MIN, 0);.
    There is an invariant I maintained in my original code, which is the max path starting from the current node (path in my code, curHeight in yours?) is non-negative. So I would change cur.curHeight = max(leftHeight, rightHeight) + root->val to cur.curHeight = max(0, max(left.curHeight, right.curHeight)+root->val).
    It'll also be easier to understand your code if you could provide the pathInfo struct with comments.


  • 0
    S

Log in to reply
 

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