Thursday, January 5, 2012

Difference Between Sums of Odd and Even Levels in Binary Trees

Question: calculate the difference between the sum of nodes at even level and sum of nodes at odd level.
Solution: recursion is the easiest way to solve this problem. At each non-null node of the tree, we have three things to do. 1) Find the difference between the node's left child with it's children by calling the function recursively on the node's left child. 2) Do the same thing for the node's right child. 3) Find the difference between the current node and the sum of it's left and right child.

public int diffBetween(pRootNode)
{
   if (pRootNode === null || pRootNode === undefined) 
      return 0;

   int lvalue = diffBetween(pRootNode.left);
   int rvalue = diffBetween(pRootNode.rigjavascript:void(0)ht);

   int result = pRootNode.data - (lvalue + rvalue);
   return result;
}
Explanation: the method takes in the root node of the binary tree that users want to compute the difference.

0 comments:

Post a Comment