Dado un árbol binario y un Node. La tarea es buscar y verificar si el Node dado existe en el árbol binario o no. Si existe, escriba SÍ; de lo contrario, escriba NO.
Árbol binario dado :
Ejemplos :
Input: Node = 4 Output: YES Input: Node = 40 Output: NO
La idea es usar cualquiera de los recorridos del árbol para recorrer el árbol y, mientras lo atraviesa, verificar si el Node actual coincide con el Node dado. Imprima SÍ si algún Node coincide con el Node dado y deja de atravesar más y si el árbol está completamente atravesado y ninguno de los Nodes coincide con el Node dado, imprima NO.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check if a node exists
// in a binary tree
#include <iostream>
using namespace std;
// Binary tree node
struct Node {
int data;
struct Node *left, *right;
Node(int data)
{
this->data = data;
left = right = NULL;
}
};
// Function to traverse the tree in preorder
// and check if the given node exists in it
bool ifNodeExists(struct Node* node, int key)
{
if (node == NULL)
return false;
if (node->data == key)
return true;
/* then recur on left subtree */
bool res1 = ifNodeExists(node->left, key);
// node found, no need to look further
if(res1) return true;
/* node is not found in left,
so recur on right subtree */
bool res2 = ifNodeExists(node->right, key);
return res2;
}
// Driver Code
int main()
{
struct Node* root = new Node(0);
root->left = new Node(1);
root->left->left = new Node(3);
root->left->left->left = new Node(7);
root->left->right = new Node(4);
root->left->right->left = new Node(8);
root->left->right->right = new Node(9);
root->right = new Node(2);
root->right->left = new Node(5);
root->right->right = new Node(6);
int key = 4;
if (ifNodeExists(root, key))
cout << "YES";
else
cout << "NO";
return 0;
}
Java
// Java program to check if a node exists
// in a binary tree
class GFG
{
// Binary tree node
static class Node
{
int data;
Node left, right;
Node(int data)
{
this.data = data;
left = right = null;
}
};
// Function to traverse the tree in preorder
// and check if the given node exists in it
static boolean ifNodeExists( Node node, int key)
{
if (node == null)
return false;
if (node.data == key)
return true;
// then recur on left subtree /
boolean res1 = ifNodeExists(node.left, key);
// node found, no need to look further
if(res1) return true;
// node is not found in left,
// so recur on right subtree /
boolean res2 = ifNodeExists(node.right, key);
return res2;
}
// Driver Code
public static void main(String args[])
{
Node root = new Node(0);
root.left = new Node(1);
root.left.left = new Node(3);
root.left.left.left = new Node(7);
root.left.right = new Node(4);
root.left.right.left = new Node(8);
root.left.right.right = new Node(9);
root.right = new Node(2);
root.right.left = new Node(5);
root.right.right = new Node(6);
int key = 4;
if (ifNodeExists(root, key))
System.out.println("YES");
else
System.out.println("NO");
}
}
// This code is contributed by Arnab Kundu
Python3
"""Python program to check if a node exists
in a binary tree."""
# A Binary Tree Node
# Utility function to create a new tree node
class newNode:
# Constructor to create a newNode
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Function to traverse the tree in preorder
# and check if the given node exists in it
def ifNodeExists(node, key):
if (node == None):
return False
if (node.data == key):
return True
""" then recur on left subtree """
res1 = ifNodeExists(node.left, key)
# node found, no need to look further
if res1:
return True
""" node is not found in left,
so recur on right subtree """
res2 = ifNodeExists(node.right, key)
return res2
# Driver Code
if __name__ == '__main__':
root = newNode(0)
root.left = newNode(1)
root.left.left = newNode(3)
root.left.left.left = newNode(7)
root.left.right = newNode(4)
root.left.right.left = newNode(8)
root.left.right.right = newNode(9)
root.right = newNode(2)
root.right.left = newNode(5)
root.right.right = newNode(6)
key = 4
if (ifNodeExists(root, key)):
print("YES" )
else:
print("NO")
# This code is contributed by SHUBHAMSINGH10
C#
// C# program to check if a node exists
// in a binary tree
using System;
class GFG
{
// Binary tree node
public class Node
{
public int data;
public Node left, right;
public Node(int data)
{
this.data = data;
left = right = null;
}
};
// Function to traverse the tree in preorder
// and check if the given node exists in it
static bool ifNodeExists( Node node, int key)
{
if (node == null)
return false;
if (node.data == key)
return true;
// then recur on left subtree /
bool res1 = ifNodeExists(node.left, key);
// node found, no need to look further
if(res1) return true;
// node is not found in left,
// so recur on right subtree /
bool res2 = ifNodeExists(node.right, key);
return res2;
}
// Driver Code
public static void Main(String []args)
{
Node root = new Node(0);
root.left = new Node(1);
root.left.left = new Node(3);
root.left.left.left = new Node(7);
root.left.right = new Node(4);
root.left.right.left = new Node(8);
root.left.right.right = new Node(9);
root.right = new Node(2);
root.right.left = new Node(5);
root.right.right = new Node(6);
int key = 4;
if (ifNodeExists(root, key))
Console.WriteLine("YES");
else
Console.WriteLine("NO");
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// javascript program to check if a node exists
// in a binary tree // Binary tree node
class Node {
constructor(data) {
this.data = data;
this.left = this.right = null;
}
}
// Function to traverse the tree in preorder
// and check if the given node exists in it
function ifNodeExists(node , key) {
if (node == null)
return false;
if (node.data == key)
return true;
// then recur on left subtree /
var res1 = ifNodeExists(node.left, key);
// node found, no need to look further
if (res1)
return true;
// node is not found in left,
// so recur on right subtree /
var res2 = ifNodeExists(node.right, key);
return res2;
}
// Driver Code
var root = new Node(0);
root.left = new Node(1);
root.left.left = new Node(3);
root.left.left.left = new Node(7);
root.left.right = new Node(4);
root.left.right.left = new Node(8);
root.left.right.right = new Node(9);
root.right = new Node(2);
root.right.left = new Node(5);
root.right.right = new Node(6);
var key = 4;
if (ifNodeExists(root, key))
document.write("YES");
else
document.write("NO");
// This code is contributed by todaysgaurav
</script>
Producción
YES
Complejidad de tiempo: O(N), ya que estamos usando recursividad para atravesar N Nodes del árbol.
Espacio auxiliar: O(N), no estamos usando ningún espacio adicional explícito, pero como estamos usando recursividad, habrá espacio adicional asignado para la pila recursiva.