5
\$\begingroup\$

This code is attributed to Stack Overflow itself here. The path which adds to the sum, which need not be starting from the root, not be ending at the leaf, i.e. a path can be between root and a leaf.

I'm looking for code review, optimizations and best practices. I'm also looking for a solution better than \$O(n^2)\$ time complexity, if such exists. I'm also verifying space complexity to be \$O(n)\$, where \$n\$ in both the cases is the number of treenodes.

Also, the code specifically demands me to print, making unit testing not possible. Are there any pointers on how such code could be tested?

public class AllPathsAddingSum {

    private TreeNode root;

    public AllPathsAddingSum(List<Integer> items) { 
        create (items);
    };

    /**
     * Constructs a binary tree in order of elements in an array.
     * After the number of nodes in the level have maxed, the next 
     * element in the array would be a child of leftmost node.
     */
    private void create(List<Integer> items) {
        if (items.size() == 0) {
            throw new IllegalArgumentException("There should atleast be single item in the tree");
        }

        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;
        }
    }

    /**
     * Prints all the paths that add to the input value.
     * @param value the value, that all the nodes of a path should add upto.
     */
    public void printAllSumPaths(int value) { 
        traverse(root, value);
    }

    private void traverse(TreeNode node, int value) {
        if (node == null) return;

        computePaths(node, 0, value, new ArrayList<Integer>());

        traverse(node.left, value); 
        traverse(node.right, value);
    }

    private void computePaths(TreeNode node, int sum, int value, List<Integer> path) {
        if (node == null) return;

        sum = sum + node.item;
        path.add(node.item);

        if (sum == value) {
            for (Integer i : path) {
                System.out.print(i + " ");
            }
            System.out.println();
        }

        computePaths(node.left, sum, value, path);
        computePaths(node.right, sum, value, path);

        path.remove(path.size() - 1);
    }

    public static void main(String[] args) {
        AllPathsAddingSum sumPaths = new AllPathsAddingSum(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
        sumPaths.printAllSumPaths(4);

        sumPaths = new AllPathsAddingSum(Arrays.asList(1, 0, 0, -1));
        sumPaths.printAllSumPaths(0);
    }
}
\$\endgroup\$
  • \$\begingroup\$ solution for unit-testing added \$\endgroup\$ – Pimgd Jan 26 '15 at 8:29
3
\$\begingroup\$
public AllPathsAddingSum(List<Integer> items) { 
    create (items);
};

Unneeded space, unneeded semicolon. Consider autoformatting your code.

for (Integer i : path) {
    System.out.print(i + " ");
}
System.out.println();

This section in computePaths is doing something different than the function description. It doesn't calculate, it prints.

Move it to a separate method. Then give the class a PrintStream to use. This PrintStream would be System.out, or a dummy PrintStream that just copies everything to an internal buffer.

Then you can unittest your code.

\$\endgroup\$

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.