Sum of left and right nodes (individually) in a Binary Search Tree I have written a program which calculates the sum of all the left nodes and the sum of right nodes in a Binary search tree.

I have used BFS to traverse the tree. The code is as follows:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;


public class SumLeftRightNodes {


/**
 * This class represents the individual nodes of the binary tree
 * Each node has a left, right pointer of type Node
 * and Value to hold the value
 * @author Aneesh
 *
 */
static class Node {
    Node left;

    Node right;

    int value;

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node value=" + value + "";
    }

}


/**
 * This function inserts an element into the binary tree
 * @param node
 * @param value
 */
public static void insert(Node node, int value) {
    if (value &lt; node.value) {
        if (node.left != null) {
            insert(node.left, value);
        } else {
            System.out.println("  Inserted " + value + " to left of "
                    + node.value);
            node.left = new Node(value);
        }
    } else if (value &gt; node.value) {
        if (node.right != null) {
            insert(node.right, value);
        } else {
            System.out.println("  Inserted " + value + " to right of "
                    + node.value);
            node.right = new Node(value);
        }
    }
}


public static void main(String[] args) {
    // TODO Auto-generated method stub
    Node root = new Node(5);
    System.out.println("Binary Tree Example");
    System.out.println("Building tree with root value " + root.value);
    insert(root, 1);
    insert(root, 8);
    insert(root,-2);
    insert(root, 6);
    insert(root, 3);
    insert(root, 9);
    insert(root,-3);
    insert(root,-1);

    System.out.println("sum of all left and right nodes is as follows\n");
    sumOfLeftandRightNodes(root);
}

public static void sumOfLeftandRightNodes(Node root) {
    // TODO Auto-generated method stub
    long leftSum = 0, rightSum = 0;

    Queue&lt;Node&gt; nodes = new LinkedList&lt;Node&gt;();

    //add the root to the Queue
    nodes.add(root);

    List&lt;Node&gt; leftNodes = new ArrayList&lt;Node&gt;() , rightNodes = new ArrayList&lt;Node&gt;();

    while (!nodes.isEmpty()){

        //BFS traversal
        Node temp = nodes.poll();

        //if left child is present then add the value of the node to the left Count
        if (temp.left!=null){
            leftSum += temp.left.value;
            leftNodes.add(temp.left);
            nodes.add(temp.left);
        }
        //if right child is present then add the value of the node to the right Count
        if (temp.right!=null){
            rightSum += temp.right.value;
            nodes.add(temp.right);
            rightNodes.add(temp.right);
        }
    }

    System.out.println("left = "+leftNodes+" \nRight Nodes = "+rightNodes);
    System.out.println("left sum ="+leftSum+"\nRight sum="+rightSum);
}

}


Any suggestion and improvements are welcome. If there is an easier method to this problem then I would like to know.
This code works and it seems quite fine.


  If there is an easier method to this problem then I would like to know.


You could do it without a Queue,
using a recursive solution,
if your tree is not too deep to lead to a stack overflow.
But since you need to track two kinds of values,
you would need to accumulate them in a helper object,
for example:

private static class Result {
    private long leftSum;
    private long rightSum;
}

public static void sumOfLeftandRightNodes(Node node, Result result) {
    if (node.left != null) {
        result.leftSum += node.left.value;
        sumOfLeftandRightNodes(node.left, result);
    }
    if (node.right != null) {
        result.rightSum += node.right.value;
        sumOfLeftandRightNodes(node.right, result);
    }
}


You could call this method with:

Result result = new Result();
sumOfLeftandRightNodes(root, result);


One advantage of this method is that the solution will become unit-testable,
thanks to this helper class.
When the above call returns, you could add test cases to validate your solution,
for example:

assertEquals(2, result.leftSum);
assertEquals(19, result.rightSum);


Coding style

I would recommend to make everything private when you can,
and final when you can.
The Node class also has a bit too much vertical spacing:


static class Node {
    Node left;

    Node right;

    int value;



I suggest to write this way:

private static class Node {
    private Node left;
    private Node right;
    private final int value;




In the breadth-first search implementation,
temp for the loop variable is not a great name.
I recommend to rename it to node.