Given a binary tree, the task is to find the sum of all the nodes whose parent is even.
Examples:
Input:
1
/ \
3 8
/ \
5 6
/
1
Output: 11
The only even nodes are 8 and 6 and
the sum of their children is 5 + 6 = 11.
Input:
2
/ \
3 8
/ / \
2 5 6
/ \
1 3
Output: 25
3 + 8 + 5 + 6 + 3 = 25
Approach: Initialise sum = 0 and perform a recursive traversal of the tree and check if the node is even or not, if the node is even then add the values of its children to the sum. Finally, print the sum.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// A binary tree nodestruct Node { int data; struct Node *left, *right;};// A utility function to allocate a new nodestruct Node* newNode(int data){ struct Node* newNode = new Node; newNode->data = data; newNode->left = newNode->right = NULL; return (newNode);}// This function visit each node in preorder fashion// And adds the values of the children of a node with// even value to the res variablevoid calcSum(Node* root, int& res){ // Base Case if (root == NULL) return; // If the value of the // current node if even if (root->data % 2 == 0) { // If the left child of the even // node exist then add it to the res if (root->left) res += root->left->data; // Do the same with the right child if (root->right) res += root->right->data; } // Visiting the left subtree and the right // subtree just like preorder traversal calcSum(root->left, res); calcSum(root->right, res);}// Function to return the sum of nodes// whose parent has even valueint findSum(Node* root){ // Initialize result int res = 0; calcSum(root, res); return res;}// Driver codeint main(){ // Creating the tree struct Node* root = newNode(2); root->left = newNode(3); root->right = newNode(8); root->left->left = newNode(2); root->right->left = newNode(5); root->right->right = newNode(6); root->right->left->left = newNode(1); root->right->right->right = newNode(3); // Print the required sum cout << findSum(root); return 0;} |
Java
// Java implementation of the approachclass GFG{// A binary tree nodestatic class Node { int data; Node left, right;};static int res;// A utility function to allocate a new nodestatic Node newNode(int data){ Node newNode = new Node(); newNode.data = data; newNode.left = newNode.right = null; return (newNode);}// This function visit each node in preorder fashion// And adds the values of the children of a node with// even value to the res variablestatic void calcSum(Node root){ // Base Case if (root == null) return; // If the value of the // current node if even if (root.data % 2 == 0) { // If the left child of the even // node exist then add it to the res if (root.left != null) res += root.left.data; // Do the same with the right child if (root.right != null) res += root.right.data; } // Visiting the left subtree and the right // subtree just like preorder traversal calcSum(root.left); calcSum(root.right);}// Function to return the sum of nodes// whose parent has even valuestatic int findSum(Node root){ // Initialize result res = 0; calcSum(root); return res;}// Driver codepublic static void main(String[] args){ // Creating the tree Node root = newNode(2); root.left = newNode(3); root.right = newNode(8); root.left.left = newNode(2); root.right.left = newNode(5); root.right.right = newNode(6); root.right.left.left = newNode(1); root.right.right.right = newNode(3); // Print the required sum System.out.print(findSum(root));}}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 implementation of the approach result = 0;# A binary tree node class Node : def __init__(self,data) : self.data = data; self.left = None self.right = None; # This function visit each node in preorder fashion # And adds the values of the children of a node with # even value to the res variable def calcSum(root, res) : global result; # Base Case if (root == None) : return; # If the value of the # current node if even if (root.data % 2 == 0) : # If the left child of the even # node exist then add it to the res if (root.left) : res += root.left.data; result = res; # Do the same with the right child if (root.right) : res += root.right.data; result = res; # Visiting the left subtree and the right # subtree just like preorder traversal calcSum(root.left, res); calcSum(root.right, res);# Function to return the sum of nodes # whose parent has even value def findSum(root) : res = 0; calcSum(root, res); print(result) # Driver code if __name__ == "__main__" : # Creating the tree root = Node(2); root.left = Node(3); root.right = Node(8); root.left.left = Node(2); root.right.left = Node(5); root.right.right = Node(6); root.right.left.left = Node(1); root.right.right.right = Node(3); # Print the required sum findSum(root); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approachusing System;class GFG{// A binary tree nodeclass Node { public int data; public Node left, right;};static int res;// A utility function to allocate a new nodestatic Node newNode(int data){ Node newNode = new Node(); newNode.data = data; newNode.left = newNode.right = null; return (newNode);}// This function visit each node in preorder fashion// And adds the values of the children of a node with// even value to the res variablestatic void calcSum(Node root){ // Base Case if (root == null) return; // If the value of the // current node if even if (root.data % 2 == 0) { // If the left child of the even // node exist then add it to the res if (root.left != null) res += root.left.data; // Do the same with the right child if (root.right != null) res += root.right.data; } // Visiting the left subtree and the right // subtree just like preorder traversal calcSum(root.left); calcSum(root.right);}// Function to return the sum of nodes// whose parent has even valuestatic int findSum(Node root){ // Initialize result res = 0; calcSum(root); return res;}// Driver codepublic static void Main(String[] args){ // Creating the tree Node root = newNode(2); root.left = newNode(3); root.right = newNode(8); root.left.left = newNode(2); root.right.left = newNode(5); root.right.right = newNode(6); root.right.left.left = newNode(1); root.right.right.right = newNode(3); // Print the required sum Console.Write(findSum(root));}}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript implementation of the approach// A binary tree nodeclass Node { constructor() { this.data = 0; this.left = null; this.right = null; }};var res = 0;// A utility function to allocate a new nodefunction newNode(data){ var newNode = new Node(); newNode.data = data; newNode.left = newNode.right = null; return (newNode);}// This function visit each node in preorder fashion// And adds the values of the children of a node with// even value to the res variablefunction calcSum(root){ // Base Case if (root == null) return; // If the value of the // current node if even if (root.data % 2 == 0) { // If the left child of the even // node exist then add it to the res if (root.left != null) res += root.left.data; // Do the same with the right child if (root.right != null) res += root.right.data; } // Visiting the left subtree and the right // subtree just like preorder traversal calcSum(root.left); calcSum(root.right);}// Function to return the sum of nodes// whose parent has even valuefunction findSum(root){ // Initialize result res = 0; calcSum(root); return res;}// Driver code// Creating the treevar root = newNode(2);root.left = newNode(3);root.right = newNode(8);root.left.left = newNode(2);root.right.left = newNode(5);root.right.right = newNode(6);root.right.left.left = newNode(1);root.right.right.right = newNode(3);// Print the required sumdocument.write(findSum(root));</script> |
Output
25
Time Complexity: O(n) where n is number of nodes in the given Binary Tree.
Auxiliary space: O(n) for call stack as it is using recursion
Approach 2: Iterative approach using BFS traversal
In this approach, we can perform a Breadth First Search (BFS) traversal of the binary tree using a queue data structure. For each node, we check if the parent node value is even and then add the values of its left and right child nodes if they exist. We continue the BFS traversal until we process all the nodes.
- In this approach, we use a queue to store the nodes to be processed in a BFS traversal.
- We initially push the root node onto the queue, and then for each level of the tree, we process all the nodes in that level by dequeuing them from the queue.
- For each node, we check if its parent value is even,
- and if so, we add the values of its left and right child nodes to the sum and enqueue them onto the queue.
- Otherwise, we just enqueue its child nodes onto the queue without adding their values to the sum.
- We continue the BFS traversal until we have processed all the nodes in the tree.
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// A binary tree nodestruct Node { int data; struct Node *left, *right;};// A utility function to allocate a new nodestruct Node* newNode(int data){ struct Node* newNode = new Node; newNode->data = data; newNode->left = newNode->right = NULL; return (newNode);}// This function visit each node in preorder fashion// And adds the values of the children of a node with// even value to the res variableint sumEvenParent(Node* root) { if (root == nullptr) { return 0; } int sum = 0; queue<Node*> q; q.push(root); while (!q.empty()) { int n = q.size(); for (int i = 0; i < n; i++) { Node* node = q.front(); q.pop(); if (node->data % 2 == 0) { if (node->left != nullptr) { sum += node->left->data; q.push(node->left); } if (node->right != nullptr) { sum += node->right->data; q.push(node->right); } } else { if (node->left != nullptr) { q.push(node->left); } if (node->right != nullptr) { q.push(node->right); } } } } return sum;}// Driver codeint main(){ // Creating the tree struct Node* root = newNode(2); root->left = newNode(3); root->right = newNode(8); root->left->left = newNode(2); root->right->left = newNode(5); root->right->right = newNode(6); root->right->left->left = newNode(1); root->right->right->right = newNode(3); // Print the required sum cout << sumEvenParent(root); return 0;} |
Output
25
The time complexity of this approach is O(n), where n is the number of nodes in the binary tree, since we need to visit each node once in the worst case.
The space complexity of this approach is O(w), where w is the maximum width of the binary tree, since at any point in time, the queue will hold at most w nodes.
In the worst case, the width of the binary tree is n/2, so the space complexity is O(n).
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!
