3
\$\begingroup\$

I want you to pick my code apart and give me some feedback on how I could make it better or more simple.

public class MaxSumPath {

    private TreeNode root;

    private static class TreeNode {
        TreeNode left;
        TreeNode right;
        int item;

        TreeNode (TreeNode left, TreeNode right, int item) {
            this.left = left;
            this.right = right;
            this.item = item;
        }
    }

    private static class TreeInfo {
        TreeNode node;
        int maxCount;

        TreeInfo (TreeNode node, int maxCount) {
            this.node = node;
            this.maxCount = maxCount;
        }
    }

    public void maxSumPath () {
        final TreeInfo treeInfo = new TreeInfo(null, 0);
        fetchMaxSumPath(root, treeInfo, root.item);
        printPath (root, treeInfo);
    }

    private void fetchMaxSumPath (TreeNode node, TreeInfo treeInfo, int sumSoFar) {
        if (node == null) return;

        sumSoFar = sumSoFar + node.item;

        if (node.right == null && node.left == null) {
            if (sumSoFar > treeInfo.maxCount) {
                treeInfo.maxCount = sumSoFar;
                treeInfo.node = node;
            }
            return;
        }

        fetchMaxSumPath(node.left, treeInfo, sumSoFar);
        fetchMaxSumPath(node.right, treeInfo, sumSoFar);
    }

    private boolean printPath (TreeNode node, TreeInfo treeInfo) {
        if (node != null &&  (node == treeInfo.node || printPath(node.left, treeInfo) || printPath(node.right, treeInfo))) {
            System.out.print(node.item + ", ");
            return true;
        }
        return false;
    }
}

Also considering additional storage (TreeInfo), is it right to say that the space complexity is \$O(1)\$?

\$\endgroup\$
2
\$\begingroup\$

You should have a constructor MaxSumPath(TreeNode root). Otherwise, there's no way for any other class to call the code.

The TreeNode(left, right, item) constructor is awkward. Consider rearranging the TreeNode constructor arguments to TreeNode(left, item, right) or TreeNode(item, left, right). I suggest creating a TreeNode(item) constructor as well.

Your TreeInfo could be eliminated by moving its variables into MaxSumPath itself. I'd rename the variables to TreeNode maxLeaf and int maxSum.

In the maxSumPath() method, you call fetchMaxSumPath(root, treeInfo, root.item). It should be fetchMaxSumPath(root, treeInfo, 0) if you don't want to double-count the root node. (Fortunately, this bug happens not to affect the output.)

The space complexity is actually O(log n) when you take into account the stack used in recursion. The time complexity is O(n), because you visit every node once when discovering the leaf for the path with the maximum sum, and every node again to find that leaf for printing. You might want to use O(log n) space (which, remember, happens anyway due to the recursion stack) to keep track of the best path while discovering the best sum, which lets you avoid the second pass O(n) pass.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Agree on constructor, agree on the double counting bug. \$\endgroup\$ – JavaDeveloper Sep 28 '13 at 7:57
  • \$\begingroup\$ Disagree on - keeping a instance variable for max count, because maintining that value will be complicated if new nodes get added or deleting from tree, I would appreciate if you could highlight if my method had pressing drawbacks, in addition to suggestions. \$\endgroup\$ – JavaDeveloper Sep 28 '13 at 7:59
  • 1
    \$\begingroup\$ I see no reason to treat what I call maxLeaf and maxSum any differently from root. Either make them all instance variables of MaxSumPath (my preferred option), all encapsulated in TreeInfo, or pass them all around as local parameters (my least preferred option). \$\endgroup\$ – 200_success Sep 28 '13 at 15:48
  • 1
    \$\begingroup\$ TreeInfo adds O(1) space on top of the O(log n) stack that I mentioned, bringing the total space to O(log n). \$\endgroup\$ – 200_success Sep 28 '13 at 15:49
  • 2
    \$\begingroup\$ Correction — O(log n) is a best-case scenario, because the tree may not be balanced. It could be O(n) in the worst case. \$\endgroup\$ – 200_success Sep 28 '13 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.