Given a Binary Tree, calculate the sum of nodes with even valued Grandparents.
Examples:
Input:
22
/ \
3 8
/ \ / \
4 8 1 9
\
2
Output: 24
Explanation
The nodes 4, 8, 2, 1, 9
has even value grandparents.
Hence sum = 4 + 8 + 1 + 9 + 2 = 24.
Input:
1
/ \
2 3
/ \ / \
4 5 6 7
/
8
Output: 8
Explanation
Only 8 has 2 as a grandparent.
Approach: To solve the problem mentioned above, for each node that is not null, check if they have a grandparent and if their grandparent is even valued add the node’s data to the sum.
Below is the implementation of the above approach:
C++
// C++ implementation to find sum// of all the child nodes with// even grandparents in a Binary Tree#include <bits/stdc++.h>using namespace std;/* A binary tree node has data andpointers to the right and left children*/struct TreeNode { int data; TreeNode *left, *right; TreeNode(int x) { data = x; left = right = NULL; }};// Function to calculate the sumvoid getSum( TreeNode* curr, TreeNode* p, TreeNode* gp, int& sum){ // Base condition if (curr == NULL) return; // Check if node has a grandparent // if it does check // if they are even valued if (gp != NULL && gp->data % 2 == 0) sum += curr->data; // Recurse for left child getSum(curr->left, curr, p, sum); // Recurse for right child getSum(curr->right, curr, p, sum);}// Driver Programint main(){ TreeNode* root = new TreeNode(22); root->left = new TreeNode(3); root->right = new TreeNode(8); root->left->left = new TreeNode(4); root->left->right = new TreeNode(8); root->right->left = new TreeNode(1); root->right->right = new TreeNode(9); root->right->right->right = new TreeNode(2); int sum = 0; getSum(root, NULL, NULL, sum); cout << sum << '\n'; return 0;} |
Java
// Java implementation to find sum// of all the child nodes with// even grandparents in a Binary Treeimport java.util.*;class GFG{/* A binary tree node has data andpointers to the right and left children*/static class TreeNode { int data; TreeNode left, right; TreeNode(int x) { data = x; left = right = null; }} static int sum = 0; // Function to calculate the sumstatic void getSum(TreeNode curr, TreeNode p, TreeNode gp){ // Base condition if (curr == null) return; // Check if node has // a grandparent // if it does check // if they are even valued if (gp != null && gp.data % 2 == 0) sum += curr.data; // Recurse for left child getSum(curr.left, curr, p); // Recurse for right child getSum(curr.right, curr, p);}// Driver Programpublic static void main(String[] args){ TreeNode root = new TreeNode(22); root.left = new TreeNode(3); root.right = new TreeNode(8); root.left.left = new TreeNode(4); root.left.right = new TreeNode(8); root.right.left = new TreeNode(1); root.right.right = new TreeNode(9); root.right.right.right = new TreeNode(2); getSum(root, null, null); System.out.println(sum);}}// This code is contributed by Rajput-Ji |
Python3
# Python3 implementation to find sum# of all the child nodes with# even grandparents in a Binary Tree# A binary tree node has data and# pointers to the right and left children class TreeNode(): def __init__(self, data): self.data = data self.left = None self.right = Nonesum = 0# Function to calculate the sumdef getSum(curr, p, gp): global sum # Base condition if (curr == None): return # Check if node has a grandparent # if it does check # if they are even valued if (gp != None and gp.data % 2 == 0): sum += curr.data # Recurse for left child getSum(curr.left, curr, p) # Recurse for right child getSum(curr.right, curr, p) # Driver codeif __name__=="__main__": root = TreeNode(22) root.left = TreeNode(3) root.right = TreeNode(8) root.left.left = TreeNode(4) root.left.right = TreeNode(8) root.right.left = TreeNode(1) root.right.right = TreeNode(9) root.right.right.right = TreeNode(2) getSum(root, None, None) print(sum)# This code is contributed by rutvik_56 |
C#
// C# implementation to find sum// of all the child nodes with// even grandparents in a Binary Treeusing System;class GFG{/* A binary tree node has data and pointers to the right and left children*/class TreeNode { public int data; public TreeNode left, right; public TreeNode(int x) { data = x; left = right = null; }} static int sum = 0; // Function to calculate the sumstatic void getSum(TreeNode curr, TreeNode p, TreeNode gp){ // Base condition if (curr == null) return; // Check if node has // a grandparent // if it does check // if they are even valued if (gp != null && gp.data % 2 == 0) sum += curr.data; // Recurse for left child getSum(curr.left, curr, p); // Recurse for right child getSum(curr.right, curr, p);}// Driver Programpublic static void Main(String[] args){ TreeNode root = new TreeNode(22); root.left = new TreeNode(3); root.right = new TreeNode(8); root.left.left = new TreeNode(4); root.left.right = new TreeNode(8); root.right.left = new TreeNode(1); root.right.right = new TreeNode(9); root.right.right.right = new TreeNode(2); getSum(root, null, null); Console.WriteLine(sum);}}// This code is contributed by Princi Singh |
Javascript
<script> // JavaScript implementation to find sum // of all the child nodes with // even grandparents in a Binary Tree /* A binary tree node has data and pointers to the right and left children*/ class TreeNode { constructor(x) { this.left = null; this.right = null; this.data = x; } } let sum = 0; // Function to calculate the sum function getSum(curr, p, gp) { // Base condition if (curr == null) return; // Check if node has // a grandparent // if it does check // if they are even valued if (gp != null && gp.data % 2 == 0) sum += curr.data; // Recurse for left child getSum(curr.left, curr, p); // Recurse for right child getSum(curr.right, curr, p); } let root = new TreeNode(22); root.left = new TreeNode(3); root.right = new TreeNode(8); root.left.left = new TreeNode(4); root.left.right = new TreeNode(8); root.right.left = new TreeNode(1); root.right.right = new TreeNode(9); root.right.right.right = new TreeNode(2); getSum(root, null, null); document.write(sum);</script> |
Output:
24
Time Complexity: O(N)
Space Complexity: O(H), Used by recursion stack where H = height of the tree.
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!
