Thursday, August 18, 2011

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. Here is the implementation in JavaScript:

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

   var lvalue = diffBetween(pRootNode.pLChild);
   var rvalue = diffBetween(pRootNode.pRChild);

   var result = pRootNode.nData - (lvalue + rvalue);
   return result;
}

Explanation: the method takes in the root node of the binary tree that users want to compute the difference. Here are the steps:

  1. Line 3 and 2, check for invalid input. This step acts as the case stopper for our recursion.
  2. Line 6: find the difference between the left child and its children.
  3. Line 7: find the difference between the right child and its children.
  4. Line 9: find the difference between the current node and its children.
  5. Line 10: finally returns the result.

If you have any comment, please post. Also if there is any part that is not clear, please also let me know :)

3 comments:

  1. Could anyone show the recursion tracing of this input tree?
    level 1 = 5
    level 2 = 3 9
    level 3 = 2 4 8 12

    my tracing is
    5,3,2,4,9,8,12. Is it correct?

    ReplyDelete
  2. Yes your tracing is correct. This algorithm is basically a depth first search.

    ReplyDelete
  3. Can you please explain step by step on how this will be resolved in recursion?

    ReplyDelete