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)\$?