Java solution for sum of paths of binary tree

Overview

In this article we will see the Java solution for the Sum Paths problem mention in Perl Weekly Challenge. This wonderful website is developed and maintained by one of my very near and dear friend Mohammad Sajid Anwar.

We need to find the sum of all the paths from roof to leaf in a binary tree.

Code

We will recursively iterate through the children of the tree till we find the leaf node. Once we have find the leaf node we will add the elements in the path array. Below is the java solution for the problem:

SumPath.java

public class SumPath {

    private int sum = 0;

    public void sumOfAllPaths(TreeNode node, int[] path, int len) {
        if (node == null) {
            return;
        }
        path[len] = node.data;
        len++;
        if (node.left == null && node.right == null) {
            for (int i = 0; i < path.length; i++) {
                sum += path[i];
            }
            return;
        }
        sumOfAllPaths(node.left, path, len);
        sumOfAllPaths(node.right, path, len);
    }

    public int getSum() {
        return sum;
    }

    static class TreeNode {
        public int data;
        public TreeNode left;
        public TreeNode right;

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

Test

Below are two simple tests for the above solution:

SumPathTest.java

import org.junit.Before;
import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class SumPathTest {

    private SumPath sumPath;

    @Before
    public void setUp() {
        sumPath = new SumPath();
    }

    /**
     *      1
     *     /
     *    2
     *   / \
     *  3   4
     */
    @Test
    public void test1() {
        SumPath.TreeNode node1 = new SumPath.TreeNode(3, null, null);
        SumPath.TreeNode node2 = new SumPath.TreeNode(4, null, null);
        SumPath.TreeNode node3 = new SumPath.TreeNode(2, node1, node2);
        SumPath.TreeNode node4 = new SumPath.TreeNode(1, node3, null);

        sumPath.sumOfAllPaths(node4, new int[4], 0);
        assertEquals(13, sumPath.getSum());
    }

    /**
     *      1
     *     / \
     *    2   3
     *   /   / \
     *  4   5   6
     */
    @Test
    public void test2() {
        SumPath.TreeNode node001 = new SumPath.TreeNode(4, null, null);
        SumPath.TreeNode node002 = new SumPath.TreeNode(5, null, null);
        SumPath.TreeNode node003 = new SumPath.TreeNode(6, null, null);
        SumPath.TreeNode node004 = new SumPath.TreeNode(2, node001, null);
        SumPath.TreeNode node005 = new SumPath.TreeNode(3, node002, node003);
        SumPath.TreeNode node006 = new SumPath.TreeNode(1, node004, node005);

        sumPath.sumOfAllPaths(node006, new int[6], 0);
        assertEquals(26, sumPath.getSum());
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: