Given a binary tree, the task is to find the absolute difference between the even valued and the odd valued nodes in a binary tree.
Examples:
Input: 5 / \ 2 6 / \ \ 1 4 8 / / \ 3 7 9 Output: 5 Explanation: Sum of the odd value nodes is: 5 + 1 + 3 + 7 + 9 = 25 Sum of the even value nodes is: 2 + 6 + 4 + 8 = 20 Absolute difference = (25 – 20) = 5. Input: 4 / \ 1 4 / \ \ 7 2 6 Output: 8
Approach:
Follow the steps below to solve the problem:
- Traverse each node in the tree and check if the value at that node is odd or even.
- Update oddSum and evenSum accordingly after visiting each node.
- After complete traversal of the tree, print the absolute difference between oddSum and evenSum.
Below is the implementation of the above approach:
C++
// C++ implementation of // the above approach #include <bits/stdc++.h> using namespace std; int oddsum = 0; int evensum = 0; int ans = 0; struct node { int data; struct node* left; struct node* right; }; struct node* newnode( int data) { node* temp = new node(); temp->data = data; temp->left = temp->right = NULL; return temp; } // Function calculate the sum of // odd and even value node void OddEvenDifference( struct node* root) { // If root is NULL if (root == NULL) { return ; } else { // Check if current root // is odd or even if (root->data % 2 == 0) { evensum += root->data; } else { oddsum += root->data; } // Call on the left subtree OddEvenDifference(root->left); // Call on the right subtree OddEvenDifference(root->right); } } // Driver Code int main() { node* root = newnode(5); root->left = newnode(2); root->right = newnode(6); root->left->left = newnode(1); root->left->right = newnode(4); root->left->right->left = newnode(3); root->right->right = newnode(8); root->right->right->right = newnode(9); root->right->right->left = newnode(7); OddEvenDifference(root); cout << abs (oddsum - evensum) << endl; } |
Java
// Java implementation of // the above approach class GFG{ static int oddsum = 0 ; static int evensum = 0 ; static int ans = 0 ; static class node { int data; node left; node right; }; static node newnode( int data) { node temp = new node(); temp.data = data; temp.left = temp.right = null ; return temp; } // Function calculate the sum of // odd and even value node static void OddEvenDifference(node root) { // If root is null if (root == null ) { return ; } else { // Check if current root // is odd or even if (root.data % 2 == 0 ) { evensum += root.data; } else { oddsum += root.data; } // Call on the left subtree OddEvenDifference(root.left); // Call on the right subtree OddEvenDifference(root.right); } } // Driver Code public static void main(String[] args) { node root = newnode( 5 ); root.left = newnode( 2 ); root.right = newnode( 6 ); root.left.left = newnode( 1 ); root.left.right = newnode( 4 ); root.left.right.left = newnode( 3 ); root.right.right = newnode( 8 ); root.right.right.right = newnode( 9 ); root.right.right.left = newnode( 7 ); OddEvenDifference(root); System.out.print(Math.abs( oddsum - evensum) + "\n" ); } } // This code is contributed by amal kumar choubey |
Python3
# Python3 implementation of # the above approach oddsum = 0 evensum = 0 class Node: def __init__( self , data): self .left = None self .right = None self .data = data def newnode(data): temp = Node(data) return temp # Function calculate the sum of # odd and even value node def OddEvenDifference(root): global evensum, oddsum # If root is NULL if (root = = None ): return else : # Check if current root # is odd or even if (root.data % 2 = = 0 ): evensum + = root.data else : oddsum + = root.data # Call on the left subtree OddEvenDifference(root.left) # Call on the right subtree OddEvenDifference(root.right) # Driver code if __name__ = = "__main__" : root = newnode( 5 ) root.left = newnode( 2 ) root.right = newnode( 6 ) root.left.left = newnode( 1 ) root.left.right = newnode( 4 ) root.left.right.left = newnode( 3 ) root.right.right = newnode( 8 ) root.right.right.right = newnode( 9 ) root.right.right.left = newnode( 7 ) OddEvenDifference(root) print ( abs (oddsum - evensum)) # This code is contributed by rutvik_56 |
C#
// C# implementation of // the above approach using System; class GFG{ static int oddsum = 0; static int evensum = 0; //static int ans = 0; class node { public int data; public node left; public node right; }; static node newnode( int data) { node temp = new node(); temp.data = data; temp.left = temp.right = null ; return temp; } // Function calculate the sum of // odd and even value node static void OddEvenDifference(node root) { // If root is null if (root == null ) { return ; } else { // Check if current root // is odd or even if (root.data % 2 == 0) { evensum += root.data; } else { oddsum += root.data; } // Call on the left subtree OddEvenDifference(root.left); // Call on the right subtree OddEvenDifference(root.right); } } // Driver Code public static void Main(String[] args) { node root = newnode(5); root.left = newnode(2); root.right = newnode(6); root.left.left = newnode(1); root.left.right = newnode(4); root.left.right.left = newnode(3); root.right.right = newnode(8); root.right.right.right = newnode(9); root.right.right.left = newnode(7); OddEvenDifference(root); Console.Write(Math.Abs( oddsum - evensum) + "\n" ); } } // This code is contributed by amal kumar choubey |
Javascript
<script> // Javascript implementation of the above approach let oddsum = 0; let evensum = 0; let ans = 0; class node { constructor(data) { this .data = data; this .left = this .right = null ; } } function newnode(data) { let temp = new node(data); return temp; } // Function calculate the sum of // odd and even value node function OddEvenDifference(root) { // If root is null if (root == null ) { return ; } else { // Check if current root // is odd or even if (root.data % 2 == 0) { evensum += root.data; } else { oddsum += root.data; } // Call on the left subtree OddEvenDifference(root.left); // Call on the right subtree OddEvenDifference(root.right); } } let root = newnode(5); root.left = newnode(2); root.right = newnode(6); root.left.left = newnode(1); root.left.right = newnode(4); root.left.right.left = newnode(3); root.right.right = newnode(8); root.right.right.right = newnode(9); root.right.right.left = newnode(7); OddEvenDifference(root); document.write(Math.abs(oddsum - evensum) + "</br>" ); </script> |
Output:
5
Time Complexity: O(N) where N is the number of nodes in given Binary Tree, as it does a simple traversal of the tree.
Auxiliary Space: O(h) where h is the height of given Binary Tree due to Recursion.
Another Approach (Iterative):
We can solve this problem by level order traversal using queue.
Below is the implementation of above approach:
C++
// C++ Program for the above approach #include<bits/stdc++.h> using namespace std; // structure of node struct Node{ int data; struct Node* left = NULL; struct Node* right = NULL; Node( int data){ this ->data = data; this ->left = this ->right = NULL; } }; // Utility function to create node Node* newnode( int data){ return new Node(data); } // function to find the absolute difference int OddEvenDifference(Node* root){ int oddSum = 0; int evenSum = 0; queue<Node*> q; q.push(root); while (!q.empty()){ Node* front_node = q.front(); q.pop(); if (front_node->data % 2 == 0) evenSum += front_node->data; else oddSum += front_node->data; if (front_node->left != NULL) q.push(front_node->left); if (front_node->right != NULL) q.push(front_node->right); } return abs (oddSum - evenSum); } // Driver code int main(){ Node* root = newnode(5); root->left = newnode(2); root->right = newnode(6); root->left->left = newnode(1); root->left->right = newnode(4); root->left->right->left = newnode(3); root->right->right = newnode(8); root->right->right->right = newnode(9); root->right->right->left = newnode(7); cout<<OddEvenDifference(root); return 0; } // This code is contributed by Kirti Agarwal(kirtiagarwal23121999) |
Python3
# Python Program for the above approach import queue # structure of node class Node: def __init__( self , data): self .data = data self .left = None self .right = None # function to find the absolute difference def OddEvenDifference(root): oddSum = 0 evenSum = 0 # create a queue q = queue.Queue() q.put(root) while ( not q.empty()): front_node = q.get() # get the front node from the queue if (front_node.data % 2 = = 0 ): # if the data of the front node is even evenSum + = front_node.data # add it to the even sum else : oddSum + = front_node.data # otherwise, add it to the odd sum if (front_node.left is not None ): # if the front node has a left child q.put(front_node.left) # add it to the queue if (front_node.right is not None ): # if the front node has a right child q.put(front_node.right) # add it to the queue return abs (oddSum - evenSum) # return the absolute difference between the odd and even sums # Driver code if __name__ = = '__main__' : root = Node( 5 ) root.left = Node( 2 ) root.right = Node( 6 ) root.left.left = Node( 1 ) root.left.right = Node( 4 ) root.left.right.left = Node( 3 ) root.right.right = Node( 8 ) root.right.right.right = Node( 9 ) root.right.right.left = Node( 7 ) # call the OddEvenDifference function and print the result print (OddEvenDifference(root)) |
Java
// Java Program for the above approach import java.util.*; // structure of node class Node{ int data; Node left; Node right; Node( int data){ this .data = data; this .left = null ; this .right = null ; } }; // Driver code class Main { // function to find the absolute difference static int OddEvenDifference(Node root){ int oddSum = 0 ; int evenSum = 0 ; Queue<Node> q = new LinkedList<Node>(); q.add(root); while (!q.isEmpty()){ Node front_node = q.poll(); if (front_node.data % 2 == 0 ) evenSum += front_node.data; else oddSum += front_node.data; if (front_node.left != null ) q.add(front_node.left); if (front_node.right != null ) q.add(front_node.right); } return Math.abs(oddSum - evenSum); } public static void main(String[] args) { Node root = new Node( 5 ); root.left = new Node( 2 ); root.right = new Node( 6 ); root.left.left = new Node( 1 ); root.left.right = new Node( 4 ); root.left.right.left = new Node( 3 ); root.right.right = new Node( 8 ); root.right.right.right = new Node( 9 ); root.right.right.left = new Node( 7 ); System.out.println(OddEvenDifference(root)); } } |
Javascript
// JavaScript program for the above approach // class of tree node class Node{ constructor(data){ this .data = data; this .left = null ; this .right = null ; } } // utility function to create node function newnode(data){ return new Node(data); } // function to find the absolute difference function oddEvenDifference(root){ let oddSum = 0; let evenSum = 0; let q = []; q.push(root); while (q.length > 0){ let front_node = q.shift(); if (front_node.data % 2 == 0) evenSum += front_node.data; else oddSum += front_node.data; if (front_node.left) q.push(front_node.left); if (front_node.right) q.push(front_node.right); } return Math.abs(oddSum - evenSum); } // driver code let root = newnode(5); root.left = newnode(2); root.right = newnode(6); root.left.left = newnode(1); root.left.right = newnode(4); root.left.right.left = newnode(3); root.right.right = newnode(8); root.right.right.right = newnode(9); root.right.right.left = newnode(7); console.log(oddEvenDifference(root)); |
C#
// C# Program for the above approach using System; using System.Collections.Generic; // structure of node public class Node { public int data; public Node left = null ; public Node right = null ; public Node( int data) { this .data = data; this .left = this .right = null ; } } class MainClass { // Utility function to create node static Node newnode( int data) { return new Node(data); } // function to find the absolute difference static int OddEvenDifference(Node root) { int oddSum = 0; int evenSum = 0; Queue<Node> q = new Queue<Node>(); q.Enqueue(root); while (q.Count > 0) { Node front_node = q.Peek(); q.Dequeue(); if (front_node.data % 2 == 0) evenSum += front_node.data; else oddSum += front_node.data; if (front_node.left != null ) q.Enqueue(front_node.left); if (front_node.right != null ) q.Enqueue(front_node.right); } return Math.Abs(oddSum - evenSum); } // Driver code static void Main( string [] args) { Node root = newnode(5); root.left = newnode(2); root.right = newnode(6); root.left.left = newnode(1); root.left.right = newnode(4); root.left.right.left = newnode(3); root.right.right = newnode(8); root.right.right.right = newnode(9); root.right.right.left = newnode(7); Console.WriteLine(OddEvenDifference(root)); } } // This code is contributed by user_dtewbxkn77n |
Output
5
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!