Imprime los Nodes que están justo encima del Node hoja.

Dado un árbol binario que consta de N Nodes, la tarea es imprimir los Nodes que están justo encima del Node hoja.
Ejemplos:

Entrada: N = 7, a continuación se muestra el árbol binario dado: 
 

Salida: 20 8 12 
Explicación: 
el Node 20 está justo encima del Node hoja 22. 
El Node 8 está justo encima del Node hoja 4. 
El Node 12 está justo encima de los Nodes hoja 10 y 14.
 

Entrada: N = 5, a continuación se muestra el árbol binario dado: 
 

Salida: 1 2 
Explicación: 
el Node 1 está justo encima del Node hoja 3. 
El Node 2 está justo encima de los Nodes hoja 4 y 5.

Enfoque: La idea es atravesar el árbol y para cada Node, comprobar si puede ser el que está justo encima del Node hoja. Para eso, el Node actual debe tener hijos y al menos uno de los hijos debe ser un Node hoja. A continuación se muestran los pasos:

• Atraviesa el árbol y comprueba cada Node.
• Si el Node actual tiene dos hijos, compruebe si alguno de ellos es un Node raíz. En caso afirmativo, imprima el Node actual.
• Si el Node actual solo tiene un hijo izquierdo o derecho, compruebe si ese hijo izquierdo o derecho es un Node hoja. En caso afirmativo, imprima el Node actual.
• De lo contrario, continúe atravesando el árbol y muévase al siguiente Node.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Node of tree
struct node {
    int data;
    struct node *left, *right;
};
 
// Creates and initializes a new
// node for the tree
struct node* newnode(int data)
{
    struct node* temp = new node();
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
 
// Prints all nodes which are just
// above leaf node
void cal(struct node* root)
{
 
    // If tree is empty
    if (root == NULL) {
        return;
    }
 
    // If it is a leaf node
    if (root->left == NULL
        && root->right == NULL) {
        return;
    }
 
    // For internal nodes
    else {
 
        // If node has two children
        if (root->left != NULL
            && root->right != NULL) {
 
            if ((root->left->left == NULL
                 && root->left->right == NULL)
                || (root->right->left == NULL
                    && root->right->right == NULL)) {
 
                cout << root->data << " ";
            }
        }
 
        // If node has only left child
        if (root->left != NULL
            && root->right == NULL) {
 
            if (root->left->left == NULL
                && root->left->right == NULL) {
 
                cout << root->data << " ";
            }
        }
 
        // If node has only right child
        if (root->right != NULL
            && root->left == NULL) {
 
            if (root->right->left == NULL
                && root->right->right == NULL) {
 
                cout << root->data << " ";
            }
        }
    }
 
    // Recursively Call for left
    // and right subtree
    cal(root->left);
    cal(root->right);
}
 
// Driver Code
int main()
{
    // Construct a tree
    node* root = newnode(20);
    root->left = newnode(8);
    root->right = newnode(22);
    root->left->left = newnode(4);
    root->left->right = newnode(12);
    root->left->right->left = newnode(10);
    root->left->right->right = newnode(14);
 
    // Function Call
    cal(root);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
// Class containing the left and right
// child of current node and the
// key value
class Node
{
    int data;
    Node left, right;
 
    // Constructor of the class
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
class GFG{
     
Node root;
 
// Prints all nodes which are just
// above leaf node
static void cal(Node root)
{
 
    // If tree is empty
    if (root == null)
    {
        return;
    }
 
    // If it is a leaf node
    if (root.left == null &&
       root.right == null)
    {
        return;
    }
 
    // For internal nodes
    else
    {
 
        // If node has two children
        if (root.left != null &&
           root.right != null)
        {
            if ((root.left.left == null &&
                root.left.right == null) ||
               (root.right.left == null &&
               root.right.right == null))
            {
                System.out.print(root.data + " ");
            }
        }
 
        // If node has only left child
        if (root.left != null &&
           root.right == null)
        {
            if (root.left.left == null &&
               root.left.right == null)
            {
                System.out.print(root.data + " ");
            }
        }
 
        // If node has only right child
        if (root.right != null &&
             root.left == null)
        {
            if (root.right.left == null &&
               root.right.right == null)
            {
                System.out.print(root.data + " ");
            }
        }
    }
 
    // Recursively call for left
    // and right subtree
    cal(root.left);
    cal(root.right);
}
     
// Driver Code
public static void main (String[] args)
{
    GFG tree = new GFG();
 
    tree.root = new Node(20);
    tree.root.left = new Node(8);
    tree.root.right = new Node(22);
 
    tree.root.left.left = new Node(4);
    tree.root.left.right = new Node(12);
 
    tree.root.left.right.left = new Node(10);
    tree.root.left.right.right = new Node(14);
     
    // Function call
    cal(tree.root);
}
}
 
// This code is contributed by offbeat

# Python3 program for the
# above approach
 
# Node of tree
class newNode:
   
    def __init__(self, data):
       
        self.data = data
        self.left = None
        self.right = None
 
# Creates and initializes a new
# node for the tree
 
# Prints all nodes which are
# just above leaf node
def cal(root):
   
    # If tree is empty
    if (root == None):
        return
 
    # If it is a leaf node
    if (root.left == None and
        root.right == None):
        return
 
    # For internal nodes
    else:
       
        # If node has two children
        if (root.left != None and
            root.right != None):
            if ((root.left.left == None and
                 root.left.right == None) or
                (root.right.left == None and
                 root.right.right == None)):
                print(root.data, end = " ")
 
        # If node has only left child
        if (root.left != None and
            root.right == None):
            if (root.left.left == None and
                root.left.right == None):
                print(root.data, end = " ")
 
        # If node has only right child
        if (root.right != None and
            root.left == None):
            if (root.right.left == None and
                root.right.right == None):
                print(root.data, end = " ")
 
    # Recursively Call for left
    # and right subtree
    cal(root.left)
    cal(root.right)
 
# Driver Code
if __name__ == '__main__':
   
    # Construct a tree
    root = newNode(20)
    root.left = newNode(8)
    root.right = newNode(22)
    root.left.left = newNode(4)
    root.left.right = newNode(12)
    root.left.right.left = newNode(10)
    root.left.right.right = newNode(14)
 
    # Function Call
    cal(root)
 
# This code is contributed by SURENDRA_GANGWAR

// C# program for the above approach
using System;
 
// Class containing the left and right
// child of current node and the
// key value
class Node
{
    public int data;
    public Node left, right;
 
    // Constructor of the class
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
class GFG{   
Node root;
 
// Prints all nodes which are just
// above leaf node
static void cal(Node root)
{
    // If tree is empty
    if (root == null)
    {
        return;
    }
 
    // If it is a leaf node
    if (root.left == null &&
        root.right == null)
    {
        return;
    }
 
    // For internal nodes
    else
    {
        // If node has two children
        if (root.left != null &&
            root.right != null)
        {
            if ((root.left.left == null &&
                 root.left.right == null) ||
                (root.right.left == null &&
                 root.right.right == null))
            {
                Console.Write(root.data + " ");
            }
        }
 
        // If node has only left child
        if (root.left != null &&
            root.right == null)
        {
            if (root.left.left == null &&
                root.left.right == null)
            {
                Console.Write(root.data + " ");
            }
        }
 
        // If node has only right child
        if (root.right != null &&
            root.left == null)
        {
            if (root.right.left == null &&
                root.right.right == null)
            {
                Console.Write(root.data + " ");
            }
        }
    }
 
    // Recursively call for left
    // and right subtree
    cal(root.left);
    cal(root.right);
}
     
// Driver Code
public static void Main(String[] args)
{
    GFG tree = new GFG();
    tree.root = new Node(20);
    tree.root.left = new Node(8);
    tree.root.right = new Node(22);
    tree.root.left.left = new Node(4);
    tree.root.left.right = new Node(12);
    tree.root.left.right.left = new Node(10);
    tree.root.left.right.right = new Node(14);
     
    // Function call
    cal(tree.root);
}
}
 
// This code is contributed by Rajput-Ji

<script>
    // Javascript implementation of the above approach
     
    // Class containing the left and right
    // child of current node and the
    // key value
    class Node
    {
        constructor(item) {
           this.data = item;
           this.left = this.right = null;
        }
    }
     
    class GFG
    {
         
    }
     
    let root;
  
    // Prints all nodes which are just
    // above leaf node
    function cal(root)
    {
 
        // If tree is empty
        if (root == null)
        {
            return;
        }
 
        // If it is a leaf node
        if (root.left == null &&
           root.right == null)
        {
            return;
        }
 
        // For internal nodes
        else
        {
 
            // If node has two children
            if (root.left != null &&
               root.right != null)
            {
                if ((root.left.left == null &&
                    root.left.right == null) ||
                   (root.right.left == null &&
                   root.right.right == null))
                {
                    document.write(root.data + " ");
                }
            }
 
            // If node has only left child
            if (root.left != null &&
               root.right == null)
            {
                if (root.left.left == null &&
                   root.left.right == null)
                {
                    document.write(root.data + " ");
                }
            }
 
            // If node has only right child
            if (root.right != null &&
                 root.left == null)
            {
                if (root.right.left == null &&
                   root.right.right == null)
                {
                    document.write(root.data + " ");
                }
            }
        }
 
        // Recursively call for left
        // and right subtree
        cal(root.left);
        cal(root.right);
    }
     
    let tree = new GFG();
  
    tree.root = new Node(20);
    tree.root.left = new Node(8);
    tree.root.right = new Node(22);
  
    tree.root.left.left = new Node(4);
    tree.root.left.right = new Node(12);
  
    tree.root.left.right.left = new Node(10);
    tree.root.left.right.right = new Node(14);
      
    // Function call
    cal(tree.root);
     
</script>

20 8 12

Complejidad temporal: O(N)  
Espacio auxiliar: O(N)