Imprime los Nodes de Binary Tree teniendo un nieto

Dado un árbol binario , la tarea es imprimir los Nodes que tienen nietos.

Ejemplos: 

Aporte: 
 

Salida: 20 8 
Explicación: 
20 y 8 son los abuelos de 4, 12 y 10, 14.

Aporte: 
 

Salida: 1 
Explicación: 
1 es el abuelo de 4, 5. 

Enfoque: La idea utiliza Recursión . A continuación se muestran los pasos: 

1. Atraviesa el árbol dado en cada Node.
2. Compruebe si cada Node tiene un Node nieto o no.
3. Para cualquier Node de árbol (por ejemplo, temp ), si existe uno de los siguientes Nodes, entonces el Node actual es el Node abuelo: 
   • temp->izquierda->izquierda.
   • temperatura->izquierda->derecha.
   • temperatura->derecha->izquierda.
   • temperatura->derecha->derecha.
4. Si cualquiera de los anteriores existe para cualquier temperatura de Node , entonces la temperatura del Node es el Node abuelo.

A continuación se muestra la implementación del enfoque anterior:

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

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

1

Complejidad temporal: O(N) , donde N es el número de Nodes. 
Espacio Auxiliar: O(N)