Suma de todos los Nodes secundarios con incluso abuelos en un árbol binario

Dado un árbol binario , calcule la suma de Nodes con abuelos pares.
Ejemplos: 

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.

Enfoque: para resolver el problema mencionado anteriormente, para cada Node que no sea nulo, verifique si tienen un abuelo y si su abuelo es incluso valorado, agregue los datos del Node a la suma.
A continuación se muestra la implementación del enfoque anterior:
 

// 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 and
pointers 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 sum
void 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 Program
int 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 implementation to find sum
// of all the child nodes with
// even grandparents in a Binary Tree
import java.util.*;
class GFG{
 
/* A binary tree node has data and
pointers 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 sum
static 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 Program
public 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 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 = None
 
sum = 0
 
# Function to calculate the sum
def 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 code
if __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# implementation to find sum
// of all the child nodes with
// even grandparents in a Binary Tree
using 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 sum
static 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 Program
public 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

<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>

24

Complejidad de tiempo: O(N)
Complejidad de espacio: O(H) , Utilizado por la pila de recursión donde H = altura del árbol.