Searching a node in BST
Searching in BST means to locate a specific node in the data structure. In Binary search tree, searching a node is easy because of its a specific order. The steps of searching a node in Binary Search tree are listed as follows –
- First, compare the element to be searched with the root element of the tree.
- If root is matched with the target element, then return the node’s location.
- If it is not matched, then check whether the item is less than the root element, if it is smaller than the root element, then move to the left subtree.
- If it is larger than the root element, then move to the right subtree.
- Repeat the above procedure recursively until the match is found.
- If the element is not found or not present in the tree, then return NULL.
Now, let’s understand the searching in binary tree using an example:
Below is given a BST and we have to search for element 6.
Code:
Below is the implementation of searching in BST:
// 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 node
struct 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 BST
struct 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 BST
struct 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);
}
// 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 node
struct 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 BST
struct 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 BST
struct 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);
}
// Java program to search a given key in a given BST
class 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);
}
# Python3 function to search a given key in a given BST
class 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 BST
def 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 BST
def 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)
// Javascript function to search a given key in a given BST
class Node {
constructor(key) {
this.key = key;
this.left = null;
this.right = null;
}
}
// A utility function to insert
// a new node with given key in BST
function 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 BST
function 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);
}
Introduction to Binary Search Tree – Data Structure and Algorithm Tutorials
Binary Search Tree is a data structure used in computer science for organizing and storing data in a sorted manner. Binary search tree follows all properties of binary tree and its left child contains values less than the parent node and the right child contains values greater than the parent node. This hierarchical structure allows for efficient Searching, Insertion, and Deletion operations on the data stored in the tree.
Table of Content
- What is Binary Search Tree?
- Properties of Binary Search Tree
- Handling duplicate values in the Binary Search Tree
- Operations performed on a BST
- 1. Searching a node in BST
- 2. Insert a node into a BST
- 3. Delete a Node of BST
- 4. Traversal (Inorder traversal of BST)
- Applications of BST
- Advantages
- Disadvantages
- FAQ’s (Frequently asked questions) on Binary Search Tree: