CSharp  Java  Python  Swift  GO  WPF  Ruby  Scala  F#  JavaScript  SQL  PHP  Angular  HTML
Q. Program to search a node in a Binary Tree.Trees are the nonlinear data structure that stores data hierarchically. The tree is a collection of elements called nodes. Nodes are connected through edges and contain data. The first node of the tree is called Root. Each node may or may not have children node. The node which doesn't have any child node is called leaf. The binary tree is another kind of tree data structure in which each node can have at most two children. That is, each node in the binary tree will have data, left child and right child. Above diagram represents a binary tree in which 1 represent the root node of the tree. Node 2 has 4 as its left child and Node 3 has 5 as its left child and 6 as its right child. Nodes 4,5 and 6 are leaf nodes as they don?t have any child node. ExplanationIn this program, we will search a particular value in the binary tree. If it is present, print the message "Element is present in the binary tree" else print the message "Element is not present in the binary tree". In a nutshell, we will first compare data of root with data of node to be searched. If the match is found, set the flag to true. Else, search the node in left subtree and then in the right subtree. Algorithm
SolutionPython#Represent a node of binary tree class Node: def __init__(self,data): #Assign data to the new node, set left and right children to None self.data = data; self.left = None; self.right = None; class SearchBinaryTree: def __init__(self): #Represent the root of binary tree self.root = None; self.flag = False; #searchNode() will search for the particular node in the binary tree def searchNode(self, temp, value): #Check whether tree is empty if(self.root == None): print("Tree is empty"); else: #If value is found in the given binary tree then, set the flag to true if(temp.data == value): self.flag = True; return; #Search in left subtree if(self.flag == False and temp.left != None): self.searchNode(temp.left, value); #Search in right subtree if(self.flag == False and temp.right != None): self.searchNode(temp.right, value); bt = SearchBinaryTree(); #Add nodes to the binary tree bt.root = Node(1); bt.root.left = Node(2); bt.root.right = Node(3); bt.root.left.left = Node(4); bt.root.right.left = Node(5); bt.root.right.right = Node(6); #Search for node 5 in the binary tree bt.searchNode(bt.root, 5); if(bt.flag): print("Element is present in the binary tree"); else: print("Element is not present in the binary tree"); Output: Element is present in the binary tree C#include <stdio.h> #include <stdbool.h> #include <stdlib.h> //Represent a node of binary tree struct node{ int data; struct node *left; struct node *right; }; //Represent the root of binary tree struct node *root = NULL; static bool flag = false; //createNode() will create a new node struct node* createNode(int data){ //Create a new node struct node *newNode = (struct node*)malloc(sizeof(struct node)); //Assign data to newNode, set left and right children to NULL newNode>data = data; newNode>left = NULL; newNode>right = NULL; return newNode; } //searchNode() will search for the particular node in the binary tree void searchNode(struct node *temp, int value){ //Check whether tree is empty if(root == NULL){ printf("Tree is empty\n"); } else{ //If value is found in the given binary tree then, set the flag to true if(temp>data == value){ flag = true; return; } //Search in left subtree if(flag == false && temp>left != NULL){ searchNode(temp>left, value); } //Search in right subtree if(flag == false && temp>right != NULL){ searchNode(temp>right, value); } } } int main() { //Add nodes to the binary tree root = createNode(1); root>left = createNode(2); root>right = createNode(3); root>left>left = createNode(4); root>right>left = createNode(5); root>right>right = createNode(6); //Search for node 5 in the binary tree searchNode(root, 5); if(flag) printf("Element is present in the binary tree"); else printf("Element is not present in the binary tree"); return 0; } Output: Element is present in the binary tree JAVApublic class SearchBinaryTree { //Represent a node of binary tree public static class Node{ int data; Node left; Node right; public Node(int data){ //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } //Represent the root of binary tree public Node root; public static boolean flag = false; public SearchBinaryTree(){ root = null; } //searchNode() will search for the particular node in the binary tree public void searchNode(Node temp, int value){ //Check whether tree is empty if(root == null){ System.out.println("Tree is empty"); } else{ //If value is found in the given binary tree then, set the flag to true if(temp.data == value){ flag = true; return; } //Search in left subtree if(flag == false && temp.left != null){ searchNode(temp.left, value); } //Search in right subtree if(flag == false && temp.right != null){ searchNode(temp.right, value); } } } public static void main(String[] args) { SearchBinaryTree bt = new SearchBinaryTree(); //Add nodes to the binary tree bt.root = new Node(1); bt.root.left = new Node(2); bt.root.right = new Node(3); bt.root.left.left = new Node(4); bt.root.right.left = new Node(5); bt.root.right.right = new Node(6); //Search for node 5 in the binary tree bt.searchNode(bt.root, 5); if(flag) System.out.println("Element is present in the binary tree"); else System.out.println("Element is not present in the binary tree"); } } Output: Element is present in the binary tree C#using System; namespace Tree { public class Program { //Represent a node of binary tree public class Node<T>{ public T data; public Node<T> left; public Node<T> right; public Node(T data) { //Assign data to the new node, set left and right children to null this.data = data; this.left = null; this.right = null; } } public class SearchBinaryTree<T>{ //Represent the root of binary tree public Node<T> root; public static Boolean flag = false; public SearchBinaryTree(){ root = null; } //searchNode() will search for the particular node in the binary tree public void searchNode(Node<T> temp, T value){ //Check whether tree is empty if(root == null){ Console.WriteLine("Tree is empty"); } else{ //If value is found in the given binary tree then, set the flag to true if(temp.data.Equals(value)){ flag = true; return; } //Search in left subtree if(flag == false && temp.left != null){ searchNode(temp.left, value); } //Search in right subtree if(flag == false && temp.right != null){ searchNode(temp.right, value); } } } } public static void Main() { SearchBinaryTree<int> bt = new SearchBinaryTree<int>(); //Add nodes to the binary tree bt.root = new Node<int>(1); bt.root.left = new Node<int>(2); bt.root.right = new Node<int>(3); bt.root.left.left = new Node<int>(4); bt.root.right.left = new Node<int>(5); bt.root.right.right = new Node<int>(6); //Search for node 5 in the binary tree bt.searchNode(bt.root, 5); if(SearchBinaryTree<int>.flag) Console.WriteLine("Element is present in the binary tree"); else Console.WriteLine("Element is not present in the binary tree"); } } } Output: Element is present in the binary tree PHP<!DOCTYPE html> <html> <body> <?php //Represent a node of binary tree class Node{ public $data; public $left; public $right; function __construct($data){ //Assign data to the new node, set left and right children to NULL $this>data = $data; $this>left = NULL; $this>right = NULL; } } class SearchBinaryTree{ //Represent the root of binary tree public $root; public $flag; function __construct(){ $this>root = NULL; $this>flag = false; } //searchNode() will search for the particular node in the binary tree function searchNode($temp, $value){ //Check whether tree is empty if($this>root == NULL){ echo "Tree is empty<br>"; } else{ //If value is found in the given binary tree then, set the flag to true if($temp>data == $value){ $this>flag = true; return; } //Search in left subtree if($this>flag == false && $temp>left != NULL){ $this>searchNode($temp>left, $value); } //Search in right subtree if($this>flag == false && $temp>right != NULL){ $this>searchNode($temp>right, $value); } } } } $bt = new SearchBinaryTree(); //Add nodes to the binary tree $bt>root = new Node(1); $bt>root>left = new Node(2); $bt>root>right = new Node(3); $bt>root>left>left = new Node(4); $bt>root>right>left = new Node(5); $bt>root>right>right = new Node(6); //Search for node 5 in the binary tree $bt>searchNode($bt>root, 5); if($bt>flag) echo "Element is present in the binary tree"; else echo "Element is not present in the binary tree"; ?> </body> </html> Output: Element is present in the binary tree
Next TopicPrograms List
