google-code-prettify

Showing posts with label odd. Show all posts
Showing posts with label odd. Show all posts

Wednesday, 16 January 2013

Sum of nodes at odd and even levels of Binary Tree

Given a Binary Tree, write a function which calculates the difference between the sum of node values at odd levels and sum of node values at even levels, i.e. function(BinaryTree) = (sum of values of nodes at odd height) - (sum of values of node at even height). Consider the root node is at height 1.

int calculateDifference(BinaryTree root) {
    if (root == null) {
        return 0;
    }
    int result = root.getData() - calculateDifference(root.getLeft())
              - calculateDifference(root.getRight());
    return result;
};


The solution is short and uses recursion. The idea is that you negate all levels under the current one (the level of the current node) and you do that on each step of the recursion.

sum[l1] - (sum[l2] - (sum[l3] - (sum[l4] - ... = sum[l1] - sum[l2] + sum[l3] - sum[l4]...
Deifference between sum of nodes on even height and sum of nodes on odd height
Deifference between sum of nodes on even height and sum of nodes on odd height