Print the nodes of Binary Tree having a grandchild

0 0 6 minutes read

Given a Binary Tree, the task is to print the nodes that have grandchildren.

Examples:

Input:

Output: 20 8
Explanation:
20 and 8 are the grandparents of 4, 12 and 10, 14.

Input:

Output: 1
Explanation:
1 is the grandparent of 4, 5.

Approach: The idea uses Recursion. Below are the steps:

Traverse the given tree at every node.
Check if each node has grandchildren node or not.
For any tree node(say temp) if one of the below node exists then current node is the grandparent node:
- temp->left->left.
- temp->left->right.
- temp->right->left.
- temp->right->right.
If any of the above exist for any node temp then the node temp is the grandparent node.

Below is the implementation of the above approach:

C++

// C++ program for the above approach 
#include <bits/stdc++.h> 
using namespace std; 
  
// A Binary Tree Node 
struct node { 
    struct node *left, *right; 
    int key; 
}; 
  
// Function to create new tree node 
node* newNode(int key) 
{ 
    node* temp = new node; 
    temp->key = key; 
    temp->left = temp->right = NULL; 
    return temp; 
} 
  
// Function to print the nodes of 
// the Binary Tree having a grandchild 
void cal(struct node* root) 
{ 
    // Base case to check 
    // if the tree exists 
  
    if (root == NULL) 
        return; 
  
    else { 
  
        // Check if there is a left and 
        // right child of the curr node 
        if (root->left != NULL 
            && root->right != NULL) { 
  
            // Check for grandchildren 
            if (root->left->left != NULL 
                || root->left->right != NULL 
                || root->right->left != NULL 
                || root->right->right != NULL) { 
  
                // Print the node's key 
                cout << root->key << " "; 
            } 
        } 
  
        // Check if the left child 
        // of node is not null 
        else if (root->left != NULL) { 
  
            // Check for grandchildren 
            if (root->left->left != NULL 
                || root->left->right != NULL) { 
                cout << root->key << " "; 
            } 
        } 
  
        // Check if the right child 
        // of node is not null 
        else if (root->right != NULL) { 
  
            // Check for grandchildren 
            if (root->right->left != NULL 
                || root->right->right != NULL) { 
                cout << root->key << " "; 
            } 
        } 
  
        // Recursive call on left and 
        // right subtree 
        cal(root->left); 
        cal(root->right); 
    } 
} 
  
// Driver Code 
int main() 
{ 
    // Given Tree 
    struct node* root = newNode(1); 
    root->left = newNode(2); 
    root->right = newNode(3); 
    root->left->left = newNode(4); 
    root->left->right = newNode(5); 
  
    // Function Call 
    cal(root); 
    return 0; 
} 

Java

// Java program for the above approach 
import java.util.*; 
  
class GFG{ 
  
// A Binary Tree Node 
static class node  
{ 
    node left, right; 
    int key; 
}; 
  
// Function to create new tree node 
static node newNode(int key) 
{ 
    node temp = new node(); 
    temp.key = key; 
    temp.left = temp.right = null; 
    return temp; 
} 
  
// Function to print the nodes of 
// the Binary Tree having a grandchild 
static void cal(node root) 
{ 
      
    // Base case to check 
    // if the tree exists 
    if (root == null) 
        return; 
  
    else
    { 
          
        // Check if there is a left and 
        // right child of the curr node 
        if (root.left != null &&  
           root.right != null)  
        { 
              
            // Check for grandchildren 
            if (root.left.left != null || 
               root.left.right != null || 
               root.right.left != null || 
              root.right.right != null)  
            { 
                  
                // Print the node's key 
                System.out.print(root.key + " "); 
            } 
        } 
  
        // Check if the left child 
        // of node is not null 
        else if (root.left != null) 
        { 
              
            // Check for grandchildren 
            if (root.left.left != null ||  
               root.left.right != null)  
            { 
                System.out.print(root.key + " "); 
            } 
        } 
  
        // Check if the right child 
        // of node is not null 
        else if (root.right != null)  
        { 
              
            // Check for grandchildren 
            if (root.right.left != null ||  
               root.right.right != null)  
            { 
                System.out.print(root.key + " "); 
            } 
        } 
  
        // Recursive call on left and 
        // right subtree 
        cal(root.left); 
        cal(root.right); 
    } 
} 
  
// Driver Code 
public static void main(String[] args) 
{ 
      
    // Given Tree 
    node root = newNode(1); 
    root.left = newNode(2); 
    root.right = newNode(3); 
    root.left.left = newNode(4); 
    root.left.right = newNode(5); 
  
    // Function call 
    cal(root); 
} 
} 
  
// This code is contributed by Amit Katiyar

Python3

# Python3 program for the  
# above approach 
  
# A Binary Tree Node 
class newNode: 
    
    def __init__(self, key): 
        
        self.key = key 
        self.left = None
        self.right = None
  
# Function to print the nodes  
# of the Binary Tree having a  
# grandchild 
def cal(root): 
    
    # Base case to check 
    # if the tree exists 
    if (root == None): 
        return
  
    else: 
        # Check if there is a left  
        # and right child of the  
        # curr node 
        if (root.left != None and 
            root.right != None): 
            
            # Check for grandchildren 
            if (root.left.left != None or
                root.left.right != None or 
                root.right.left != None or 
                root.right.right != None): 
                
                # Print the node's key 
                print(root.key, end = " ") 
  
        # Check if the left child 
        # of node is not None 
        elif (root.left != None): 
            
            # Check for grandchildren 
            if (root.left.left != None or 
                root.left.right != None): 
                print(root.key, end = " ") 
  
        # Check if the right child 
        # of node is not None 
        elif(root.right != None): 
            
            # Check for grandchildren 
            if (root.right.left != None or 
                root.right.right != None): 
                print(root.key, end = " ") 
  
        # Recursive call on left and 
        # right subtree 
        cal(root.left) 
        cal(root.right) 
  
# Driver Code 
if __name__ == '__main__': 
    
    # Given Tree 
    root = newNode(1) 
    root.left = newNode(2) 
    root.right = newNode(3) 
    root.left.left = newNode(4) 
    root.left.right = newNode(5) 
  
    # Function Call 
    cal(root) 
  
# This code is contributed by SURENDRA_GANGWAR

C#

// C# program for the  
// above approach 
using System; 
class GFG{ 
  
// A Binary Tree Node 
public class node  
{ 
  public node left, right; 
  public int key; 
}; 
  
// Function to create new  
// tree node 
static node newNode(int key) 
{ 
  node temp = new node(); 
  temp.key = key; 
  temp.left = temp.right = null; 
  return temp; 
} 
  
// Function to print the  
// nodes of the Binary Tree  
// having a grandchild 
static void cal(node root) 
{ 
  // Base case to check 
  // if the tree exists 
  if (root == null) 
    return; 
    
  else
  { 
    // Check if there is a left and 
    // right child of the curr node 
    if (root.left != null &&  
        root.right != null)  
    { 
      // Check for grandchildren 
      if (root.left.left != null || 
          root.left.right != null || 
          root.right.left != null || 
          root.right.right != null)  
      { 
        // Print the node's key 
        Console.Write(root.key + " "); 
      } 
    } 
  
    // Check if the left child 
    // of node is not null 
    else if (root.left != null) 
    { 
      // Check for grandchildren 
      if (root.left.left != null ||  
          root.left.right != null)  
      { 
        Console.Write(root.key + " "); 
      } 
    } 
  
    // Check if the right child 
    // of node is not null 
    else if (root.right != null)  
    { 
      // Check for grandchildren 
      if (root.right.left != null ||  
          root.right.right != null)  
      { 
        Console.Write(root.key + " "); 
      } 
    } 
  
    // Recursive call on left and 
    // right subtree 
    cal(root.left); 
    cal(root.right); 
  } 
} 
  
// Driver Code 
public static void Main(String[] args) 
{ 
  // Given Tree 
  node root = newNode(1); 
  root.left = newNode(2); 
  root.right = newNode(3); 
  root.left.left = newNode(4); 
  root.left.right = newNode(5); 
  
  // Function call 
  cal(root); 
} 
} 
  
// This code is contributed by Princi Singh

Javascript

<script> 
    // Javascript program for the above approach 
      
    // A Binary Tree Node 
    class node 
    { 
        constructor(key) { 
           this.left = null; 
           this.right = null; 
           this.key = key; 
        } 
    } 
  
    // Function to create new tree node 
    function newNode(key) 
    { 
        let temp = new node(key); 
        return temp; 
    } 
  
    // Function to print the nodes of 
    // the Binary Tree having a grandchild 
    function cal(root) 
    { 
  
        // Base case to check 
        // if the tree exists 
        if (root == null) 
            return; 
  
        else
        { 
  
            // Check if there is a left and 
            // right child of the curr node 
            if (root.left != null && 
               root.right != null) 
            { 
  
                // Check for grandchildren 
                if (root.left.left != null || 
                   root.left.right != null || 
                   root.right.left != null || 
                  root.right.right != null) 
                { 
  
                    // Print the node's key 
                    document.write(root.key + " "); 
                } 
            } 
  
            // Check if the left child 
            // of node is not null 
            else if (root.left != null) 
            { 
  
                // Check for grandchildren 
                if (root.left.left != null || 
                   root.left.right != null) 
                { 
                    document.write(root.key + " "); 
                } 
            } 
  
            // Check if the right child 
            // of node is not null 
            else if (root.right != null) 
            { 
  
                // Check for grandchildren 
                if (root.right.left != null || 
                   root.right.right != null) 
                { 
                    document.write(root.key + " "); 
                } 
            } 
  
            // Recursive call on left and 
            // right subtree 
            cal(root.left); 
            cal(root.right); 
        } 
    } 
      
    // Given Tree 
    let root = newNode(1); 
    root.left = newNode(2); 
    root.right = newNode(3); 
    root.left.left = newNode(4); 
    root.left.right = newNode(5); 
   
    // Function call 
    cal(root); 
  
// This code is contributed by mukesh07. 
</script>

Output:

Time Complexity: O(N), where N is the number of nodes.
Auxiliary Space: 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 zambiatek!