Tutorialspoint.dev

Iterative searching in Binary Search Tree

Given a binary search tree and a key. Check the given key exist in BST or not without recursion.



Please refer binary search tree insertion for recursive search.

C++

// C++ program to demonstrate searching operation
// in binary search tree without recursion
#include<bits/stdc++.h>
using namespace std;
  
struct Node
{
    int data;
    struct Node *left, *right;
};
  
// Function to check the given key exist or not
bool iterativeSearch(struct Node *root, int key)
{
    // Traverse untill root reaches to dead end
    while (root != NULL)
    {
        // pass right subtree as new tree
        if (key > root->data)
            root = root->right;
  
        // pass left subtree as new tree
        else if (key < root->data)
            root = root->left;
        else
            return true;// if the key is found return 1
    }
    return false;
}
  
// A utility function to create a new BST Node
struct Node *newNode(int item)
{
    struct Node *temp =  new Node;
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}
  
/* A utility function to insert a new Node with
   given key in BST */
struct Node* insert(struct Node* Node, int data)
{
    /* If the tree is empty, return a new Node */
    if (Node == NULL) return newNode(data);
  
    /* Otherwise, recur down the tree */
    if (data < Node->data)
        Node->left  = insert(Node->left, data);
    else if (data > Node->data)
        Node->right = insert(Node->right, data);
  
    /* return the (unchanged) Node pointer */
    return Node;
}
  
// Driver Program to test above functions
int main()
{
    /* Let us create following BST
              50
            /   
          30      70
         /      / 
       20   40  60   80 */
    struct Node *root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);
    if (iterativeSearch(root, 15))
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

Java

// Java program to demonstrate searching operation 
// in binary search tree without recursion 
import java.util.*;
  
class GFG
{
      
static class Node 
    int data; 
    Node left, right; 
}; 
  
// Function to check the given key exist or not 
static boolean iterativeSearch( Node root, int key) 
    // Traverse untill root reaches to dead end 
    while (root != null
    
        // pass right subtree as new tree 
        if (key > root.data) 
            root = root.right; 
  
        // pass left subtree as new tree 
        else if (key < root.data) 
            root = root.left; 
        else
            return true;// if the key is found return 1 
    
    return false
  
// A utility function to create a new BST Node 
static Node newNode(int item) 
    Node temp = new Node(); 
    temp.data = item; 
    temp.left = temp.right = null
    return temp; 
  
/* A utility function to insert a new Node with 
given key in BST */
static Node insert( Node Node, int data) 
    /* If the tree is empty, return a new Node */
    if (Node == null) return newNode(data); 
  
    /* Otherwise, recur down the tree */
    if (data < Node.data) 
        Node.left = insert(Node.left, data); 
    else if (data > Node.data) 
        Node.right = insert(Node.right, data); 
  
    /* return the (unchanged) Node pointer */
    return Node; 
  
// Driver code
public static void main(String args[])
    /* Let us create following BST 
            50 
            /  
        30 70 
        / /  
    20 40 60 80 */
    Node root = null
    root = insert(root, 50); 
    insert(root, 30); 
    insert(root, 20); 
    insert(root, 40); 
    insert(root, 70); 
    insert(root, 60); 
    insert(root, 80); 
    if (iterativeSearch(root, 15)) 
        System.out.println("YES");
    else
        System.out.println("NO");
}
  
// This code is contributed by Arnab Kundu

Python3

# Python program to demonstrate searching operation 
# in binary search tree without recursion
class newNode: 
  
    # Constructor to create a new node 
    def __init__(self, data): 
        self.data = data 
        self.left = None
        self.right = None
  
# Function to check the given 
# key exist or not 
def iterativeSearch(root, key):
      
    # Traverse untill root reaches 
    # to dead end 
    while root != None:
          
        # pass right subtree as new tree 
        if key > root.data: 
            root = root.right
  
        # pass left subtree as new tree
        elif key < root.data:
            root = root.left 
        else:
            return True # if the key is found return 1 
    return False
  
# A utility function to insert a 
# new Node with given key in BST 
def insert(Node, data):
      
    # If the tree is empty, return 
    # a new Node 
    if Node == None:
        return newNode(data) 
  
    # Otherwise, recur down the tree 
    if data < Node.data: 
        Node.left = insert(Node.left, data) 
    elif data > Node.data: 
        Node.right = insert(Node.right, data)
  
    # return the (unchanged) Node pointer 
    return Node
  
# Driver Code
if __name__ == '__main__':
      
    # Let us create following BST 
    #         50 
    #     30     70 
    # / /  
    # 20 40 60 80 
    root = None
    root = insert(root, 50
    insert(root, 30
    insert(root, 20
    insert(root, 40
    insert(root, 70
    insert(root, 60
    insert(root, 80)
    if iterativeSearch(root, 15): 
        print("Yes"
    else:
        print("No"
  
# This code is contributed by PranchalK


Output:

No


This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter