Posted on by Kalkicode
Code Recursion

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

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.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment