Sum of nodes on the longest path

JavaView on GFG

Time: O(n)

Space: O(h)

Intuition

Find the sum of nodes on the longest root-to-leaf path. DFS tracking depth and sum.

Algorithm

1DFS with (depth, sum). At leaf: if depth > maxDepth: update maxDepth and maxSum. If depth == maxDepth: maxSum = max(maxSum, sum).

Common Pitfalls

•Maximize path length first; among equal-length paths, maximize sum. Single DFS pass.

Sum of nodes on the longest path.java

Java

// Approach: DFS. Track (depth, sum) from root to each leaf. Maximize depth; break ties by sum.
// Time: O(n) Space: O(h)
class Node {
    int data;
    Node left, right;

    public Node(int data) {
        this.data = data;
    }
}

class Result {
    int maxLen;
    int maxSum;

    // constructor to initialize variables
    Result() {
        maxLen = 0;
        maxSum = Integer.MIN_VALUE;
    }
}

class Solution {
    public int sumOfLongRootToLeafPath(Node root) {
        Result res = new Result();
        find(root, 0, 0, res);
        return res.maxSum;
    }

    public static void find(Node root, int currSum, int currLen, Result res) {
        if (root == null) {
            // If at a leaf or end of path
            if (currLen > res.maxLen) {
                res.maxLen = currLen;
                res.maxSum = currSum;
            } else if (currLen == res.maxLen)
                res.maxSum = Math.max(res.maxSum, currSum);

            return;
        }

        // Recursive calls for left and right subtree
        find(root.left, currSum + root.data, currLen + 1, res);
        find(root.right, currSum + root.data, currLen + 1, res);
    }
}

Was this solution helpful?