Search This Blog

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 :)

Friday, July 29, 2011

How to Reverse a String

Question: given a string, reverse it. You can destroy the original string or return a new string that is the reverse of the original string. For example, if input is "abcde", output will be "edcba".

Solution: this is a simple problem. We just need to traverse the input string from last character to the first character. As we traversing the input string, we add its characters to the output string. At the end of the traversal, we have an output string that is the reverse of the original. Here is the code in JavaScript:

function sReverseStr(pInputStr)
{
   if (pInputStr === null || pInputStr === undefined)
      return;

   var pResultStr = "";
   
   for (var i = pInputStr.length - 1; i > -1; i--)
   {
      pResultStr += pInputStr.charAt(i);
   }

   return pResultStr;
}

Code Explanation: the code is straight forward. Here is the breakdown:

  • First, we check for invalid input. Nothing new here.
  • Next, we allocate a new string named pResultStr.
  • The for loop goes through each character in the input one by one from the end to the beginning. Then we add each of those character to the new string.
  • When the for loop finishes, pResultStr is now the reverse of the input. We simply return it.

That's all for this post. Thanks for reading :)