Q:

Program to search a node in a Binary Tree

belongs to collection: Tree Programs

robaa
Save to bookmark
|
2022-11-09
|
  319 
0

Trees are the non-linear 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.

Explanation

In 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

  1. Define Node class which has three attributes namely: data left and right. Here, left represents the left child of the node and right represents the right child of the node.
  2. When a node is created, data will pass to data attribute of the node and both left and right will be set to null.
  3. Define another class which has two attribute root and flag.
    1. Root represents the root node of the tree and initializes it to null.
    2. The Flag will be used to check whether the given node is present in the tree or not. Initially, it will be set to false.
  4. searchNode() will search for a particular node in the binary tree:
    1. It checks whether the root is null, which means the tree is empty.
    2. If the tree is not empty, it will compare temp?s data with value. If they are equal, it will set the flag to true and return.
    3. Traverse left subtree by calling searchNode() recursively and check whether the value is present in left subtree.
    4. Traverse right subtree by calling searchNode() recursively and check whether the value is present in the right subtree.

Input:

Search for node 5 in the binary tree

Output:

Element is present in the binary tree
Python programming, Php programming, Java programming, C programming, c# programming, examples, Python programming examples, Php programming examples, Java programming examples, C programming examples, c# programming examples,
login and add your own answer to this question

All Answers

robaa
2022-11-09
need an explanation for this answer? contact us directly to get an explanation for this answer

Python

#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

 

JAVA

public 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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Tree Programs
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
<< Program to implement Binary Tree using the linked ...