Sum Single Children
by Isai Damier, Android Engineer @ Google

/**************************************************************************
 * Author: Isai Damier
 * Title: Sum Single Children of BST
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Time Complexity of Solution:
 *   Best = Average = Worst = O(n).
 * 
 * Description: Not every node in a BST has two children. A node
 *    may have no children at all (e.g. a leaf) or a node may
 *    have a single child. This function aggregates the values
 *    of all nodes that are single children. If the tree is null,
 *    the function returns -1.
 *
 * Technical Details: In this implementation, the root of the
 *     tree is counted as a single child.
 *
 **************************************************************************/ 
 public int sumSingleChildren() {
  if (null == root) {
    return -1;
  }
  Queue<Node> queue = new LinkedList<Node>();
  queue.add(root);
  Node n;
  int sum = root.data;//the root is a single child
  while (!queue.isEmpty()) {
    n = queue.remove();//dequeue
    if (null != n.left && null != n.right) {//nothing to add
      queue.add(n.left);
      queue.add(n.right);
    } else if (null != n.left) {
      sum += n.left.data;
      queue.add(n.left);
    } else if (null != n.right) {
      sum += n.right.data;
      queue.add(n.right);
    }//if-else if-else if
  }//while
  return sum;
}

import org.junit.Test;
import static org.junit.Assert.*;

public class BSTTest {

 /**
   * Test of sumSingleChildren method, of class BST.
   */
  @Test
  public void testSumSingleChildren() {
    System.out.println(""sumSingleChildren"");
    BST bst = new BST();
    int[] treeTape = {200, 100, 300, 50, 150, 250, 350, 25, 75, 125,
      175, 225, 275, 325, 375, 35, 212, 312, 400};
    assertEquals(-1, bst.sumSingleChildren());
    //set expectation
    int expected = 200 + 35 + 212 + 312 + 400;//draw the tree on paper

    //load data into tree
    for (int i : treeTape) {
      bst.add(i);
    }
    assertEquals(treeTape.length, bst.size());//has correct size

    //test sumSingleChildren
    assertEquals(expected, bst.sumSingleChildren());
    assertEquals(treeTape.length, bst.size());//has correct size
  }
}