Sum of left and right nodes (individually) in a Binary Search Tree

Question

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 < 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 > 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<Node> nodes = new LinkedList<Node>();
 //add the root to the Queue
 nodes.add(root);
 List<Node> leftNodes = new ArrayList<Node>() , rightNodes = new ArrayList<Node>();
 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.

Answer 1

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.