Type like pro


Binary tree sum of nodes at odd levels

Binary tree sum of nodes at odd levels


Given a binary tree find the sum of nodes present at odd levels. That means excluding nodes at every alternate levels.


We will a find the sum by recursively calling the function on left and right children of a node. While calling the function on any child node we will toggle a boolean flag to indicate whether this level is to include in the sum or not. If current level is to be included then add the current node's value to to the sum obtained from left and right children and return it. If the current level is not to be included then return only the sum of values returned from children.


public class BinaryTreeSumOfValuesAtOddHeight
 public static void main(String[] args)
  Node a = new Node(1);
  Node b = new Node(2);
  Node c = new Node(3);
  Node d = new Node(4);
  Node e = new Node(5);
  Node f = new Node(8);
  Node g = new Node(6);
  Node h = new Node(9);
  a.left = b;
  a.right = c;
  b.left = d;
  b.right = e;
  c.right = f;
  f.left = g;
  f.right = h;
  int sum = findOddLevelSum(a);

 private static int findOddLevelSum(Node a)
  return findOddLevelSum(a, true);

 private static int findOddLevelSum(Node a, boolean oddLevel)
  if (a == null)
   return 0;
  int childSum=findOddLevelSum(a.left, !oddLevel)
    + findOddLevelSum(a.right, !oddLevel);
  if (oddLevel)
   return a.value + childSum;
   return childSum;

 static class Node
  Node left;
  Node right;
  int value;

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