Sum of nodes in binary tree whose grandparents exists

The problem involves calculating the sum of nodes in a binary tree where the parent node has a grandparent node. Specifically, we want to find the sum of values of nodes in the binary tree that are grandchildren of some node.

Problem Statement

Given a binary tree, the task is to find the sum of values of nodes that are grandchildren of some node in the tree.

Example Scenario

Consider the binary tree shown below:

        4   
       /  \                          
      /    \    
     12     7    
    / \      \               
   2   3      1
      / \    / 
     6   8  5
    /        
   9  

For this tree, the nodes 2, 3, 6, 9, 8, 1, and 5 are grandchildren of some parent node. The sum of their values is 34.

Example 1
        4   
       /  \                          
      /    \    
     12     7    
    / \      \               
   2   3      1
      / \    / 
     6   8  5
    /        
   9                        
-------------------
Here node 
node key   parent  grandparents
  2        12         4
  3        12         4
  6        3         12
  8        3         12  
  9        6         3 
  1        7         4  
  5        1         7 
--------------------------
 34
--------------------------

Example 2
-----------

        4   
       /  \                          
      /    \    
     12     7    
    / \                    
   2   3      
      / \     
     6   8   
    /        
   9                        
-------------------
Here node 
node key   parent  grandparents
  2        12         4
  3        12         4
  6        3         12
  8        3         12  
  9        6         3    
--------------------------
 28
--------------------------

Idea to Solve the Problem

To solve this problem, we can use a recursive approach to traverse the binary tree and calculate the sum of values of nodes that are grandchildren. During traversal, we need to keep track of the current level in the tree. If the current level is greater than 2, we add the value of the current node to the sum.

Pseudocode

int grandchildSum(TreeNode node, int level)
{
    if (node == null)
        return 0;

    int result = 0;
    if (level > 2)
        result = node.data;

    result += grandchildSum(node.left, level + 1)
                + grandchildSum(node.right, level + 1);

    return result;
}

Algorithm Explanation

1. Implement a function grandchildSum that takes two arguments: node (current node) and level (current level in the tree).
2. Base case: If the current node is null, return 0.
3. Initialize a variable result to store the sum.
4. If the current level is greater than 2, add the value of the current node to the result.
5. Recursively calculate the sum for the left and right subtrees, increasing the level by 1.
6. Return the sum.

Code Solution

1) Sum of all the grandchild nodes of binary tree in java 2) Sum of all the grandchild nodes of binary tree in c++ 3) Sum of all the grandchild nodes of binary tree in c 4) Sum of all the grandchild nodes of binary tree in c# 5) Sum of all the grandchild nodes of binary tree in vb.net 6) Sum of all the grandchild nodes of binary tree in php 7) Sum of all the grandchild nodes of binary tree in node js 8) Sum of all the grandchild nodes of binary tree in typescript 9) Sum of all the grandchild nodes of binary tree in python 10) Sum of all the grandchild nodes of binary tree in ruby 11) Sum of all the grandchild nodes of binary tree in scala 12) Sum of all the grandchild nodes of binary tree in swift 13) Sum of all the grandchild nodes of binary tree in kotlin 14) Sum of all the grandchild nodes of binary tree in golang

Output Explanation

The code implements the algorithm and calculates the sum of values of nodes that are grandchildren of some parent node. It displays the tree nodes using pre-order traversal and prints the calculated result.

Time Complexity

The time complexity of this algorithm is O(N), where N is the number of nodes in the binary tree. This is because we visit each node exactly once during the traversal. The space complexity is O(H), where H is the height of the binary tree, due to the recursive call stack.