Iterative searching in Binary Search Tree

Last Updated : 01 Dec, 2022

Given a binary search tree and a key. Check the given key exists 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 until 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 until 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 until 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

C#

// C# program to demonstrate searching operation
// in binary search tree without recursion
using System;
 
class GFG {
 
    public class Node {
        public int data;
        public Node left, right;
    };
 
    // Function to check the given key exist or not
    static bool iterativeSearch(Node root, int key)
    {
        // Traverse until 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))
            Console.WriteLine("YES");
        else
            Console.WriteLine("NO");
    }
}
 
// This code has been contributed by 29AjayKumar

Javascript

<script>
 
// JavaScript program to 
// demonstrate searching operation
// in binary search tree without recursion
 
class Node {
    constructor() {
        this.data = 0;
        this.left = null;
        this.right = null;
    }
}
 
    // Function to check the given key exist or not
    function iterativeSearch(root , key)
    {
        // Traverse until 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
            // if the key is found return 1
                return true; 
        }
        return false;
    }
 
    // A utility function to create a new BST Node
    function newNode(item)
    {
        var 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 */
    function insert(Node , 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
     
        /* Let us create following BST 
            50 
            / \ 
        30 70 
        / \ / \ 
    20 40 60 80 */
        var 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))
            document.write("YES");
        else
            document.write("NO");
             
// This code is contributed by todaysgaurav
 
</script>

Output

No

Time Complexity: O(h), here h is the height of the BST.
Auxiliary Space: O(1), as constant extra space is used.

S

Shahnawaz_Ali

Improve

Previous Article

Self-Balancing Binary Search Trees

A program to check if a Binary Tree is BST or not

Similar Reads

Iterative Deepening Search(IDS) or Iterative Deepening Depth First Search(IDDFS)

There are two common ways to traverse a graph, BFS and DFS. Considering a Tree (or Graph) of huge height and width, both BFS and DFS are not very efficient due to following reasons. DFS first traverses nodes going through one adjacent of root, then next adjacent. The problem with this approach is, if there is a node close to root, but not in first

Check whether a binary tree is a full binary tree or not | Iterative Approach

Given a binary tree containing n nodes. The problem is to check whether the given binary tree is a full binary tree or not. A full binary tree is defined as a binary tree in which all nodes have either zero or two child nodes. Conversely, there is no node in a full binary tree, which has only one child node. Examples: Input : 1 / \ 2 3 / \ 4 5 Outp

Check if a binary tree is subtree of another binary tree using preorder traversal : Iterative

Given two binary trees S and T, the task is the check that if S is a subtree of the Tree T. For Example: Input: Tree T - 1 / \ 2 3 / \ / \ 4 5 6 7 Tree S - 2 / \ 4 5 Output: YES Explanation: The above tree is the subtree of the tree T, Hence the output is YES Approach: The idea is to traverse both the tree in Pre-order Traversal and check for each

Searching in Binary Search Tree (BST)

Given a BST, the task is to search a node in this BST. For searching a value in BST, consider it as a sorted array. Now we can easily perform search operation in BST using Binary Search Algorithm. Algorithm to search for a key in a given Binary Search Tree:Let's say we want to search for the number X, We start at the root. Then: We compare the valu

Complexity of different operations in Binary tree, Binary Search Tree and AVL tree

In this article, we will discuss the complexity of different operations in binary trees including BST and AVL trees. Before understanding this article, you should have a basic idea about Binary Tree, Binary Search Tree, and AVL Tree. The main operations in a binary tree are: search, insert and delete. We will see the worst-case time complexity of t

Iterative Search for a key 'x' in Binary Tree

Given a Binary Tree and a key to be searched in it, write an iterative method that returns true if key is present in Binary Tree, else false. For example, in the following tree, if the searched key is 3, then function should return true and if the searched key is 12, then function should return false. One thing is sure that we need to traverse comp

Binary Search Tree | Set 3 (Iterative Delete)

Given a binary search tree and a node of the binary search tree, the task is to delete the node from the Binary Search tree Iteratively.Here are the three cases that arise while performing a delete operation on a BST: 1. Case 1: Node to be deleted is a leaf node. Directly delete the node from the tree. 10 10 / \ delete(5) / \ 7 15 ---------> 7 1

Binary Search Tree vs Ternary Search Tree

For effective searching, insertion, and deletion of items, two types of search trees are used: the binary search tree (BST) and the ternary search tree (TST). Although the two trees share a similar structure, they differ in some significant ways. FeatureBinary Search Tree (BST)Ternary Search Tree (TST)NodeHere, each node has at most two children. H

Searching in Binary Indexed Tree using Binary Lifting in O(LogN)

Binary Indexed Tree (BIT) is a data structure that allows efficient queries of a range of elements in an array and updates on individual elements in O(log n) time complexity, where n is the number of elements in the array. Binary Lifting:One of the efficient techniques used to perform search operations in BIT is called Binary lifting.Binary Lifting

Binary Tree to Binary Search Tree Conversion using STL set

Given a Binary Tree, convert it to a Binary Search Tree. The conversion must be done in such a way that keeps the original structure of the Binary Tree.This solution will use Sets of C++ STL instead of array-based solution. Examples: Example 1 Input: 10 / \ 2 7 / \ 8 4 Output: 8 / \ 4 10 / \ 2 7 Example 2 Input: 10 / \ 30 15 / \ 20 5 Output: 15 / \

Article Tags :

Practice Tags :

Binary Search Tree