Given a binary tree in which each node element contains a number. Find the maximum possible sum from one leaf node to another.
The maximum sum path may or may not go through root. For example, in the following binary tree, the maximum sum is 27(3 + 6 + 9 + 0 – 1 + 10). Expected time complexity is O(n).
I'm looking for a code review, optimizations and best practices. I'm also verifying space complexity to be \$O(1)\$.
public class MaxSumTwoLeaf {
private TreeNode root;
public MaxSumTwoLeaf(List<Integer> items) {
create(items);
}
private void create (List<Integer> items) {
if (items.size() == 0) {
throw new NullPointerException("The input array is null.");
}
root = new TreeNode(items.get(0));
final Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
final int half = items.size() / 2;
for (int i = 0; i < half; i++) {
if (items.get(i) != null) {
final TreeNode current = queue.poll();
final int left = 2 * i + 1;
final int right = 2 * i + 2;
if (items.get(left) != null) {
current.left = new TreeNode(items.get(left));
queue.add(current.left);
}
if (right < items.size() && items.get(right) != null) {
current.right = new TreeNode(items.get(right));
queue.add(current.right);
}
}
}
}
private static class TreeNode {
private TreeNode left;
private int item;
private TreeNode right;
TreeNode(int item) {
this.item = item;
}
}
/**
* Returns the path with max sum between two leaves in the tree.
* If the tree does not have two leaves then the returned value is arbitrary.
*
* @return max distance between two nodes in the tree.
*/
public int maxTwoLeafDistance() {
if (root == null) {
throw new IllegalStateException("The root is not initialized");
}
return getMaxDistanceBetweenTwoLeaves (root).maxPathBetweenLeaves;
}
private static class NodeData {
/*
* 1
* / \
* 2 3
*
* For the node 1, the value of rootToLeafMaxValue will be 4.
*/
private int rootToLeafMaxValue;
/*
* 1
* / \
* 2 3
*
* For the node 1, the value of twoLeavesStatus will be true
*/
private boolean twoLeavesStatus;
/*
* 1
* / \
* 2 3
*
* For the node 1, the value of maxPathBetweenLeaves will be 5
*/
private int maxPathBetweenLeaves;
NodeData(int rootToLeafMaxValue, boolean twoLeavesStatus, int maxPathBetweenLeaves) {
this.rootToLeafMaxValue = rootToLeafMaxValue;
this.twoLeavesStatus = twoLeavesStatus;
this.maxPathBetweenLeaves = maxPathBetweenLeaves;
}
}
private NodeData getMaxDistanceBetweenTwoLeaves(TreeNode node) {
if (node == null) return new NodeData(Integer.MIN_VALUE, false, Integer.MIN_VALUE);
NodeData leftNodeData = getMaxDistanceBetweenTwoLeaves(node.left);
NodeData rightNodeData = getMaxDistanceBetweenTwoLeaves(node.right);
int treeValue = leftNodeData.rootToLeafMaxValue + rightNodeData.rootToLeafMaxValue + node.item; // value including the root.
int max = Math.max(treeValue, Math.max(leftNodeData.maxPathBetweenLeaves, rightNodeData.maxPathBetweenLeaves));
int maxPathBetweenLeaves = 0;
/*
* 1
* / \
* 2 3
*
* For node 1, leftNodeData.twoLeavesStatus == false and rightNodeData.twoLeavesStatus == false
*/
if (leftNodeData.twoLeavesStatus == false && rightNodeData.twoLeavesStatus == false) {
maxPathBetweenLeaves = treeValue;
} else
/* 1
* / \
* 2 3
* / \
* 4 5
*/
if (leftNodeData.twoLeavesStatus == false) {
maxPathBetweenLeaves = Math.max(treeValue, rightNodeData.maxPathBetweenLeaves);
} else
/* 1
* / \
* 2 3
* / \
* 4 5
*/
if (rightNodeData.twoLeavesStatus == false) {
maxPathBetweenLeaves = Math.max(treeValue, leftNodeData.maxPathBetweenLeaves);
} else
/* 1
* / \
* 2 3
* / \ / \
* 4 5 6 7
*/
if (max > treeValue) {
maxPathBetweenLeaves = max;
} else {
maxPathBetweenLeaves = treeValue;
}
return new NodeData(Math.max(leftNodeData.rootToLeafMaxValue, rightNodeData.rootToLeafMaxValue) + node.item, node.left != null && node.right != null, maxPathBetweenLeaves);
}
}
public class MaxSumTwoLeafTest {
@Test
public void test1() {
MaxSumTwoLeaf ms1 = new MaxSumTwoLeaf(Arrays.asList(-15, 5, 6, -8, 1, 3, 6));
assertEquals(15, ms1.maxTwoLeafDistance());
}
@Test
public void test2() {
MaxSumTwoLeaf ms2 = new MaxSumTwoLeaf(Arrays.asList(-15, 5, 6, -8, null, null, 6));
assertEquals(-6, ms2.maxTwoLeafDistance());
}
@Test
public void test3() {
MaxSumTwoLeaf ms3 = new MaxSumTwoLeaf(Arrays.asList(1, null, 3, null, null, null, 6));
assertEquals(10, ms3.maxTwoLeafDistance());
}
public void test4() {
MaxSumTwoLeaf ms4 = new MaxSumTwoLeaf(Arrays.asList(-1, -2, -3, -4, -5, -6, -7));
assertEquals(-11, ms4.maxTwoLeafDistance());
}
}
