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 nodevoid 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 Codeint 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 approachclass 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 nodestatic 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 Codepublic 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 approachoddsum = 0evensum = 0class 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 nodedef 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 codeif __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 approachusing 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 nodestatic 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 Codepublic 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 nodestruct 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 nodeNode* newnode(int data){ return new Node(data);}// function to find the absolute differenceint 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 codeint 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 approachimport queue# structure of nodeclass Node: def __init__(self, data): self.data = data self.left = None self.right = None# function to find the absolute differencedef 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 codeif __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 approachimport java.util.*;// structure of nodeclass Node{ int data; Node left; Node right; Node(int data){ this.data = data; this.left = null; this.right = null; }};// Driver codeclass 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 nodeclass Node{ constructor(data){ this.data = data; this.left = null; this.right = null; }}// utility function to create nodefunction newnode(data){ return new Node(data);}// function to find the absolute differencefunction 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 codelet 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 approachusing System;using System.Collections.Generic;// structure of nodepublic 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!
