Given a Binary tree and a node. The task is to search and check if the given node exists in the binary tree or not. If it exists, print YES otherwise print NO.
Given Binary Tree:
Examples:
Input: Node = 4 Output: YES Input: Node = 40 Output: NO
The idea is to use any of the tree traversals to traverse the tree and while traversing check if the current node matches with the given node. Print YES if any node matches with the given node and stop traversing further and if the tree is completely traversed and none of the node matches with the given node then print NO.
Below is the implementation of the above approach:
C++
// C++ program to check if a node exists// in a binary tree#include <iostream>using namespace std;// Binary tree nodestruct 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 itbool 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 Codeint 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 Codeif __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 treeusing 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> |
Output
YES
Complexity Analysis:
- Time Complexity: O(N), as we are using recursion to traverse N nodes of the tree.
- Auxiliary Space: O(N), we are not using any explicit extra space but as we are using recursion there will be extra space allocated for recursive stack.
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
