Imprimir primos de un Node dado en Binary Tree – Part 1

Dado un árbol binario y un Node, imprime todos los primos del Node dado. Tenga en cuenta que los hermanos no deben imprimirse.
Ejemplo: 
 

Input : root of below tree 
             1
           /   \
          2     3
        /   \  /  \
       4    5  6   7
       and pointer to a node say 5.

Output : 6, 7

La idea de encontrar primero el nivel de un Node dado usando el enfoque discutido aquí . Una vez que hayamos encontrado el nivel, podemos imprimir todos los Nodes en un nivel dado utilizando el enfoque discutido aquí . Lo único que debe cuidarse es que el hermano no debe imprimirse. Para manejar esto, cambiamos la función de impresión para que primero verifique el Node hermano e imprima solo si no es hermano.

A continuación se muestra la implementación de la idea anterior. 

C++

// C++ program to print cousins of a node
#include <bits/stdc++.h>
using namespace std;
 
// A Binary Tree Node
struct Node
{
    int data;
    Node *left, *right;
};
 
// A utility function to create a new
// Binary Tree Node
Node *newNode(int item)
{
    Node *temp = new Node;
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}
 
/* It returns level of the node if it is
present in tree, otherwise returns 0.*/
int getLevel(Node *root, Node *node, int level)
{
     
    // base cases
    if (root == NULL)
        return 0;
    if (root == node)
        return level;
 
    // If node is present in left subtree
    int downlevel = getLevel(root->left,
                             node, level + 1);
    if (downlevel != 0)
        return downlevel;
 
    // If node is not present in left subtree
    return getLevel(root->right, node, level + 1);
}
 
/* Print nodes at a given level such that
sibling of node is not printed if it exists */
void printGivenLevel(Node* root, Node *node, int level)
{
    // Base cases
    if (root == NULL || level < 2)
        return;
 
    // If current node is parent of a node
    // with given level
    if (level == 2)
    {
        if (root->left == node || root->right == node)
            return;
        if (root->left)
            cout << root->left->data << " ";
        if (root->right)
            cout << root->right->data;
    }
 
    // Recur for left and right subtrees
    else if (level > 2)
    {
        printGivenLevel(root->left, node, level - 1);
        printGivenLevel(root->right, node, level - 1);
    }
}
 
// This function prints cousins of a given node
void printCousins(Node *root, Node *node)
{
    // Get level of given node
    int level = getLevel(root, node, 1);
 
    // Print nodes of given level.
    printGivenLevel(root, node, level);
}
 
// Driver Code
int main()
{
    Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->left->right->right = newNode(15);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    root->right->left->right = newNode(8);
 
    printCousins(root, root->left->right);
 
    return 0;
}
 
// This code is contributed
// by Akanksha Rai

C

// C program to print cousins of a node
#include <stdio.h>
#include <stdlib.h>
 
// A Binary Tree Node
struct Node
{
    int data;
    Node *left, *right;
};
 
// A utility function to create a new Binary
// Tree Node
Node *newNode(int item)
{
    Node *temp =  new Node;
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}
 
/* It returns level of the node if it is present
   in tree, otherwise returns 0.*/
int getLevel(Node *root, Node *node, int level)
{
    // base cases
    if (root == NULL)
        return 0;
    if (root == node)
        return level;
 
    // If node is present in left subtree
    int downlevel = getLevel(root->left, node, level+1);
    if (downlevel != 0)
        return downlevel;
 
    // If node is not present in left subtree
    return getLevel(root->right, node, level+1);
}
 
/* Print nodes at a given level such that sibling of
   node is not printed if it exists  */
void printGivenLevel(Node* root, Node *node, int level)
{
    // Base cases
    if (root == NULL || level < 2)
        return;
 
    // If current node is parent of a node with
    // given level
    if (level == 2)
    {
        if (root->left == node || root->right == node)
            return;
        if (root->left)
           printf("%d ", root->left->data);
        if (root->right)
           printf("%d ", root->right->data);
    }
 
    // Recur for left and right subtrees
    else if (level > 2)
    {
        printGivenLevel(root->left, node, level-1);
        printGivenLevel(root->right, node, level-1);
    }
}
 
// This function prints cousins of a given node
void printCousins(Node *root, Node *node)
{
    // Get level of given node
    int level = getLevel(root, node, 1);
 
    // Print nodes of given level.
    printGivenLevel(root, node, level);
}
 
// Driver Program to test above functions
int main()
{
    Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->left->right->right = newNode(15);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    root->right->left->right = newNode(8);
 
    printCousins(root, root->left->right);
 
    return 0;
}

Java

// Java program to print cousins of a node
class GfG {
 
// A Binary Tree Node
static class Node
{
    int data;
    Node left, right;
}
 
// A utility function to create a new Binary
// Tree Node
static Node newNode(int item)
{
    Node temp = new Node();
    temp.data = item;
    temp.left = null;
    temp.right = null;
    return temp;
}
 
/* It returns level of the node if it is present
in tree, otherwise returns 0.*/
static int getLevel(Node root, Node node, int level)
{
    // base cases
    if (root == null)
        return 0;
    if (root == node)
        return level;
 
    // If node is present in left subtree
    int downlevel = getLevel(root.left, node, level+1);
    if (downlevel != 0)
        return downlevel;
 
    // If node is not present in left subtree
    return getLevel(root.right, node, level+1);
}
 
/* Print nodes at a given level such that sibling of
node is not printed if it exists */
static void printGivenLevel(Node root, Node node, int level)
{
    // Base cases
    if (root == null || level < 2)
        return;
 
    // If current node is parent of a node with
    // given level
    if (level == 2)
    {
        if (root.left == node || root.right == node)
            return;
        if (root.left != null)
        System.out.print(root.left.data + " ");
        if (root.right != null)
        System.out.print(root.right.data + " ");
    }
 
    // Recur for left and right subtrees
    else if (level > 2)
    {
        printGivenLevel(root.left, node, level-1);
        printGivenLevel(root.right, node, level-1);
    }
}
 
// This function prints cousins of a given node
static void printCousins(Node root, Node node)
{
    // Get level of given node
    int level = getLevel(root, node, 1);
 
    // Print nodes of given level.
    printGivenLevel(root, node, level);
}
 
// Driver Program to test above functions
public static void main(String[] args)
{
    Node root = newNode(1);
    root.left = newNode(2);
    root.right = newNode(3);
    root.left.left = newNode(4);
    root.left.right = newNode(5);
    root.left.right.right = newNode(15);
    root.right.left = newNode(6);
    root.right.right = newNode(7);
    root.right.left.right = newNode(8);
 
    printCousins(root, root.left.right);
}
}

Python3

# Python3 program to print cousins of a node
 
# A utility function to create a new
# Binary Tree Node
class newNode:
    def __init__(self, item):
        self.data = item
        self.left = self.right = None
 
# It returns level of the node if it is
# present in tree, otherwise returns 0.
def getLevel(root, node, level):
     
    # base cases
    if (root == None):
        return 0
    if (root == node):
        return level
 
    # If node is present in left subtree
    downlevel = getLevel(root.left, node,
                               level + 1)
    if (downlevel != 0):
        return downlevel
 
    # If node is not present in left subtree
    return getLevel(root.right, node, level + 1)
 
# Print nodes at a given level such that
# sibling of node is not printed if
# it exists
def printGivenLevel(root, node, level):
     
    # Base cases
    if (root == None or level < 2):
        return
 
    # If current node is parent of a
    # node with given level
    if (level == 2):
        if (root.left == node or
            root.right == node):
            return
        if (root.left):
            print(root.left.data, end = " ")
        if (root.right):
            print(root.right.data, end = " ")
 
    # Recur for left and right subtrees
    else if (level > 2):
        printGivenLevel(root.left, node, level - 1)
        printGivenLevel(root.right, node, level - 1)
 
# This function prints cousins of a given node
def printCousins(root, node):
     
    # Get level of given node
    level = getLevel(root, node, 1)
 
    # Print nodes of given level.
    printGivenLevel(root, node, level)
 
# Driver Code
if __name__ == '__main__':
    root = newNode(1)
    root.left = newNode(2)
    root.right = newNode(3)
    root.left.left = newNode(4)
    root.left.right = newNode(5)
    root.left.right.right = newNode(15)
    root.right.left = newNode(6)
    root.right.right = newNode(7)
    root.right.left.right = newNode(8)
 
    printCousins(root, root.left.right)
     
# This code is contributed by PranchalK

C#

// C# program to print cousins of a node
using System;
 
public class GfG
{
 
// A Binary Tree Node
class Node
{
    public int data;
    public Node left, right;
}
 
// A utility function to create 
// a new Binary Tree Node
static Node newNode(int item)
{
    Node temp = new Node();
    temp.data = item;
    temp.left = null;
    temp.right = null;
    return temp;
}
 
/* It returns level of the node
if it is present in tree,
 otherwise returns 0.*/
static int getLevel(Node root,
            Node node, int level)
{
    // base cases
    if (root == null)
        return 0;
    if (root == node)
        return level;
 
    // If node is present in left subtree
    int downlevel = getLevel(root.left, node, level + 1);
    if (downlevel != 0)
        return downlevel;
 
    // If node is not present in left subtree
    return getLevel(root.right, node, level + 1);
}
 
/* Print nodes at a given level
such that sibling of node is
 not printed if it exists */
static void printGivenLevel(Node root,
                    Node node, int level)
{
    // Base cases
    if (root == null || level < 2)
        return;
 
    // If current node is parent of a node with
    // given level
    if (level == 2)
    {
        if (root.left == node || root.right == node)
            return;
        if (root.left != null)
            Console.Write(root.left.data + " ");
        if (root.right != null)
            Console.Write(root.right.data + " ");
    }
 
    // Recur for left and right subtrees
    else if (level > 2)
    {
        printGivenLevel(root.left, node, level - 1);
        printGivenLevel(root.right, node, level - 1);
    }
}
 
// This function prints cousins of a given node
static void printCousins(Node root, Node node)
{
    // Get level of given node
    int level = getLevel(root, node, 1);
 
    // Print nodes of given level.
    printGivenLevel(root, node, level);
}
 
// Driver code
public static void Main(String[] args)
{
    Node root = newNode(1);
    root.left = newNode(2);
    root.right = newNode(3);
    root.left.left = newNode(4);
    root.left.right = newNode(5);
    root.left.right.right = newNode(15);
    root.right.left = newNode(6);
    root.right.right = newNode(7);
    root.right.left.right = newNode(8);
 
    printCousins(root, root.left.right);
}
}
 
// This code is contributed Rajput-Ji

Javascript

<script>
  
// JavaScript program to print cousins of a node
 
// A Binary Tree Node
class Node
{
  constructor()
  {
    this.data=0;
    this.left= null;
    this.right = null;
  }
}
 
// A utility function to create 
// a new Binary Tree Node
function newNode(item)
{
    var temp = new Node();
    temp.data = item;
    temp.left = null;
    temp.right = null;
    return temp;
}
 
/* It returns level of the node
if it is present in tree,
 otherwise returns 0.*/
function getLevel(root, node, level)
{
    // base cases
    if (root == null)
        return 0;
    if (root == node)
        return level;
 
    // If node is present in left subtree
    var downlevel = getLevel(root.left, node, level + 1);
    if (downlevel != 0)
        return downlevel;
 
    // If node is not present in left subtree
    return getLevel(root.right, node, level + 1);
}
 
/* Print nodes at a given level
such that sibling of node is
 not printed if it exists */
function printGivenLevel(root, node, level)
{
    // Base cases
    if (root == null || level < 2)
        return;
 
    // If current node is parent of a node with
    // given level
    if (level == 2)
    {
        if (root.left == node || root.right == node)
            return;
        if (root.left != null)
            document.write(root.left.data + " ");
        if (root.right != null)
            document.write(root.right.data + " ");
    }
 
    // Recur for left and right subtrees
    else if (level > 2)
    {
        printGivenLevel(root.left, node, level - 1);
        printGivenLevel(root.right, node, level - 1);
    }
}
 
// This function prints cousins of a given node
function printCousins(root, node)
{
    // Get level of given node
    var level = getLevel(root, node, 1);
 
    // Print nodes of given level.
    printGivenLevel(root, node, level);
}
 
// Driver code
var root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(5);
root.left.right.right = newNode(15);
root.right.left = newNode(6);
root.right.right = newNode(7);
root.right.left.right = newNode(8);
printCousins(root, root.left.right);
 
</script>
Producción

6 7

Complejidad de tiempo : O(n)

¿Podemos resolver este problema usando un solo recorrido? Consulte el artículo a continuación 
Imprimir primos de un Node determinado en Binary Tree | Travesía única

Este artículo es una contribución de Shivam Gupta . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *