Given a BST, the task is to delete 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 value to be searched with the value of the root.
- If it’s equal we are done with the search if it’s smaller we know that we need to go to the left subtree because in a binary search tree all the elements in the left subtree are smaller and all the elements in the right subtree are larger.
- Repeat the above step till no more traversal is possible
- If at any iteration, key is found, return True. Else False.
Illustration of searching in a BST:
See the illustration below for a better understanding:
Program to implement search in BST:
C++
// C++ function to search a given key in a given BST#include <iostream>using namespace std;struct node { int key; struct node *left, *right;};// A utility function to create a new BST nodestruct node* newNode(int item){ struct node* temp = new struct node; temp->key = item; temp->left = temp->right = NULL; return temp;}// A utility function to insert// a new node with given key in BSTstruct node* insert(struct node* node, int key){ // If the tree is empty, return a new node if (node == NULL) return newNode(key); // Otherwise, recur down the tree if (key < node->key) node->left = insert(node->left, key); else if (key > node->key) node->right = insert(node->right, key); // Return the (unchanged) node pointer return node;}// Utility function to search a key in a BSTstruct node* search(struct node* root, int key){ // Base Cases: root is null or key is present at root if (root == NULL || root->key == key) return root; // Key is greater than root's key if (root->key < key) return search(root->right, key); // Key is smaller than root's key return search(root->left, key);}// Driver Codeint main(){ 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); // Key to be found int key = 6; // Searching in a BST if (search(root, key) == NULL) cout << key << " not found" << endl; else cout << key << " found" << endl; key = 60; // Searching in a BST if (search(root, key) == NULL) cout << key << " not found" << endl; else cout << key << " found" << endl; return 0;} |
C
// C function to search a given key in a given BST#include <stdio.h>#include <stdlib.h>struct node { int key; struct node *left, *right;};// A utility function to create a new BST nodestruct node* newNode(int item){ struct node* temp = (struct node*)malloc(sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp;}// A utility function to insert// a new node with given key in BSTstruct node* insert(struct node* node, int key){ // If the tree is empty, return a new node if (node == NULL) return newNode(key); // Otherwise, recur down the tree if (key < node->key) node->left = insert(node->left, key); else if (key > node->key) node->right = insert(node->right, key); // Return the (unchanged) node pointer return node;}// Utility function to search a key in a BSTstruct node* search(struct node* root, int key){ // Base Cases: root is null or key is present at root if (root == NULL || root->key == key) return root; // Key is greater than root's key if (root->key < key) return search(root->right, key); // Key is smaller than root's key return search(root->left, key);}// Driver Codeint main(){ 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); // Key to be found int key = 6; // Searching in a BST if (search(root, key) == NULL) printf("%d not found\n", key); else printf("%d found\n", key); key = 60; // Searching in a BST if (search(root, key) == NULL) printf("%d not found\n", key); else printf("%d found\n", key); return 0;} |
Java
// Java program to search a given key in a given BSTclass Node { int key; Node left, right; public Node(int item) { key = item; left = right = null; }}class BinarySearchTree { Node root; // Constructor BinarySearchTree() { root = null; } // A utility function to insert // a new node with given key in BST Node insert(Node node, int key) { // If the tree is empty, return a new node if (node == null) { node = new Node(key); return node; } // Otherwise, recur down the tree if (key < node.key) node.left = insert(node.left, key); else if (key > node.key) node.right = insert(node.right, key); // Return the (unchanged) node pointer return node; } // Utility function to search a key in a BST Node search(Node root, int key) { // Base Cases: root is null or key is present at root if (root == null || root.key == key) return root; // Key is greater than root's key if (root.key < key) return search(root.right, key); // Key is smaller than root's key return search(root.left, key); } // Driver Code public static void main(String[] args) { BinarySearchTree tree = new BinarySearchTree(); // Inserting nodes tree.root = tree.insert(tree.root, 50); tree.insert(tree.root, 30); tree.insert(tree.root, 20); tree.insert(tree.root, 40); tree.insert(tree.root, 70); tree.insert(tree.root, 60); tree.insert(tree.root, 80); // Key to be found int key = 6; // Searching in a BST if (tree.search(tree.root, key) == null) System.out.println(key + " not found"); else System.out.println(key + " found"); key = 60; // Searching in a BST if (tree.search(tree.root, key) == null) System.out.println(key + " not found"); else System.out.println(key + " found"); }} |
Python3
# Python3 function to search a given key in a given BSTclass Node: # Constructor to create a new node def __init__(self, key): self.key = key self.left = None self.right = None# A utility function to insert# a new node with the given key in BSTdef insert(node, key): # If the tree is empty, return a new node if node is None: return Node(key) # Otherwise, recur down the tree if key < node.key: node.left = insert(node.left, key) elif key > node.key: node.right = insert(node.right, key) # Return the (unchanged) node pointer return node# Utility function to search a key in a BSTdef search(root, key): # Base Cases: root is null or key is present at root if root is None or root.key == key: return root # Key is greater than root's key if root.key < key: return search(root.right, key) # Key is smaller than root's key return search(root.left, key)# Driver Codeif __name__ == '__main__': root = None root = insert(root, 50) insert(root, 30) insert(root, 20) insert(root, 40) insert(root, 70) insert(root, 60) insert(root, 80) # Key to be found key = 6 # Searching in a BST if search(root, key) is None: print(key, "not found") else: print(key, "found") key = 60 # Searching in a BST if search(root, key) is None: print(key, "not found") else: print(key, "found") |
C#
// C# function to search a given key in a given BSTusing System;public class Node { public int key; public Node left, right;}public class BinaryTree { // A utility function to create a new BST node public Node NewNode(int item) { Node temp = new Node(); temp.key = item; temp.left = temp.right = null; return temp; } // A utility function to insert // a new node with given key in BST public Node Insert(Node node, int key) { // If the tree is empty, return a new node if (node == null) return NewNode(key); // Otherwise, recur down the tree if (key < node.key) node.left = Insert(node.left, key); else if (key > node.key) node.right = Insert(node.right, key); // Return the (unchanged) node pointer return node; } // Utility function to search a key in a BST public Node Search(Node root, int key) { // Base Cases: root is null or key is present at root if (root == null || root.key == key) return root; // Key is greater than root's key if (root.key < key) return Search(root.right, key); // Key is smaller than root's key return Search(root.left, key); } // Driver Code public static void Main() { Node root = null; BinaryTree bt = new BinaryTree(); root = bt.Insert(root, 50); bt.Insert(root, 30); bt.Insert(root, 20); bt.Insert(root, 40); bt.Insert(root, 70); bt.Insert(root, 60); bt.Insert(root, 80); // Key to be found int key = 6; // Searching in a BST if (bt.Search(root, key) == null) Console.WriteLine(key + " not found"); else Console.WriteLine(key + " found"); key = 60; // Searching in a BST if (bt.Search(root, key) == null) Console.WriteLine(key + " not found"); else Console.WriteLine(key + " found"); }} |
Javascript
// Javascript function to search a given key in a given BSTclass Node { constructor(key) { this.key = key; this.left = null; this.right = null; }}// A utility function to insert// a new node with given key in BSTfunction insert(node, key) { // If the tree is empty, return a new node if (node === null) { return new Node(key); } // Otherwise, recur down the tree if (key < node.key) { node.left = insert(node.left, key); } else if (key > node.key) { node.right = insert(node.right, key); } // Return the (unchanged) node pointer return node;}// Utility function to search a key in a BSTfunction search(root, key) { // Base Cases: root is null or key is present at root if (root === null || root.key === key) { return root; } // Key is greater than root's key if (root.key < key) { return search(root.right, key); } // Key is smaller than root's key return search(root.left, key);}// Driver Codelet root = null;root = insert(root, 50);insert(root, 30);insert(root, 20);insert(root, 40);insert(root, 70);insert(root, 60);insert(root, 80);// Key to be foundlet key = 6;// Searching in a BSTif (search(root, key) === null) { console.log(key + " not found");} else { console.log(key + " found");}key = 60;// Searching in a BSTif (search(root, key) === null) { console.log(key + " not found");} else { console.log(key + " found");} |
Output
6 not found 60 found
Time complexity: O(h), where h is the height of the BST.
Auxiliary Space: O(h), where h is the height of the BST. This is because the maximum amount of space needed to store the recursion stack would be h.
Related Links:
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!
