Difference between sum of nodes at even level and sum of nodes at odd level in a Binary Tree

Problem Statement :

Given a binary tree, write a code that returns the difference between sum of nodes at even level and sum of nodes at odd level. Root is considered at level 0.

Solution :
This can be solved recursively. The bottom up approach is followed. Subtract the root with difference of its right and left nodes...


Here is the C# Code running Code. Just Copy and paste on VS..


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace diffOddAndEvenLevel
{
    // Tree Node Definition
    public class Tree
    {
        public int item;
        public Tree left;
        public Tree right;
        public Tree(int val)
        {
            item = val;
            left = null;
            right = null;
        }
    }

    // Program 
    class Program
    {
        static void Main(string[] args)
        {
            /* Constructed binary tree is
         10
       /   \
     7      30
   /  \    /
 4     8  16
/
2
*/
            Tree root = new Tree(10);
            root.left = new Tree(7);
            root.right = new Tree(30);
            root.left.left = new Tree(4);
            root.left.right = new Tree(8);
            root.right.left = new Tree(16);
            root.left.left.left = new Tree(2);
            Console.WriteLine(diffLevels(root));
        }
      
       // Function calculating the difference
        public static int diffLevels(Tree root)
        {
            if (root == null)
            {
                return 0;
            }
           // Subtracting the value from root and difference from its right and left..
            return root.item - diffLevels(root.left) - diffLevels(root.right);
        }

    }
}

Complexity :
Time Complexity :  O(n) , Since every node is visited only once and solution is bottom up approach..


Hope you liked it.. Please leave the comments below...