Tuesday 22 September 2015

Binary tree sum of nodes at odd levels

Problem


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

Solution


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.

Code

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);
  System.out.println(sum);
 }

 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;
  else
   return childSum;
 }

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

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

}

No comments:

Post a Comment