# Searching A Node In Binary Search Tree

The logic behind searching a node in a BST is as follows:

• In a binary search tree,
- Left child of a parent node < Parent node
- Right child of a parent > Parent node.
Based on the above criteria, we traverse the BST comparing the node to be searched with the root,
• We go to the left if the node to be searched is less than the parent.
• We go to the right if the node to be searched is greater than the parent.

Example : If we are to search node ( 7 ), we compare it with root node ( 5 ). As node ( 7 ) is greater than node ( 5 ), we move to the right of root node i.e we now search the right sub-tree.

Time complexity of searching a node in a BST with N nodes :
Worst-case time complexity is O ( N ), if the tree is linear; i.e to search in a BST that is linear (unbalanced) all the nodes will have to be traversed and compared.
Best-case time complexity is O ( log N ), if the tree is balanced, i.e for a balanced BST the height would be log N, and hence log N comparisons would be needed before a node is found in the tree.

Program for searching a node in a BST

from typing import Optional # For annotations

class Node :

def __init__(self, data=0, left_node=None, right_node=None) :
self.data = data
self.left = left_node
self.right = right_node

class Tree :

def SearchBST (self, root: Optional[Node], data: int) -> Optional[Node] :
if (root == None or root.data == data) :
return root
elif (root.data < data) :
return self.SearchBST(root.right, data)
elif (root.data > data) :
return self.SearchBST(root.left, data)
return None

if __name__ == "__main__" :

#     6
#    / \
#   4   9

node4 = Node(4)
node9 = Node(9)
root_node6 = Node(4, node4, node9)

t = Tree()

data = 9
if (t.SearchBST(root_node6, data) != None) :
print( "Node " + str(data) + " found")

#     5
#    / \
#   1   7
#        \
#         8

node1 = Node(1)
node8 = Node(8)
node7 = Node(7, None, node8)
root_node5 = Node(5, node1, node7)

data = 7
if (t.SearchBST(root_node5, data) != None) :
print( "Node " + str(data) + " found")

data = 10
if (t.SearchBST(root_node5, data) != None) :
print( "Node " + str(data) + " found")

Output

Node 9 found
Node 7 found
#include<iostream>
#include<vector>
using namespace std;

class Node {

public:
int data;
Node * left;
Node * right;
Node(int x) : data(x), left(NULL), right(NULL)
{}
Node(int x, Node* left_node, Node* right_node) : data(x), left(left_node), right(right_node)
{}
};

class Tree {

public:
Node * SearchBST(Node * root, int data) {
if (root == NULL or root->data == data) {
return root;
} else if (root->data < data) {
return SearchBST(root->right, data);
} else if (root->data > data) {
return SearchBST(root->left, data);
}
return NULL;
}
};

int main() {

/*   6
/ \
4   9  */

Node node4(4), node9(9);
Node root_node6(4, &node4, &node9);

Tree t;
int data = 9;
if (t.SearchBST(&root_node6, data) != NULL) {
cout << "Node " << data << " found" << endl;
}

/*   5
/ \
1   7
\
8  */

Node node1(1), node8(8);
Node node7(7, nullptr, &node8);
Node root_node5(5, &node1, &node7);

data = 7;
if (t.SearchBST(&root_node5, data) != NULL) {
cout << "Node " << data << " found" << endl;
}

data = 10;
if (t.SearchBST(&root_node5, data) != NULL) {
cout << "Node " << data << " found" << endl;
}

return 0;
}

Output

Node 9 found.
Node 7 found.
class Tree {

Node SearchBST (Node root, int data) {

if (root == null || root.data == data) {
return root;
} else if (root.data < data) {
return SearchBST(root.right, data);
} else if (root.data > data) {
return SearchBST(root.left, data);
}
return null;
}

static class Node {
int data;
Node left;
Node right;
Node () {}
Node (int x) { this.data = x; }
Node (int x, Node left_node, Node right_node) {
data = x;
left =  left_node;
right = right_node;
}
}

public static void main (String[] args) {

/*   6
/ \
4   9  */

Node node4 = new Node(4);
Node node9 = new Node(9);
Node root_node6 = new Node(4, node4, node9);

Tree t = new Tree();

int data = 9;
if (t.SearchBST(root_node6, data) != null) {
System.out.println( "Node " + data + " found");
}

/*   5
/ \
1   7
\
8  */

Node node1 = new Node(1);
Node node8 = new Node(8);
Node node7 = new Node(7, null, node8);
Node root_node5 = new Node(5, node1, node7);

data = 7;
if (t.SearchBST(root_node5, data) != null) {
System.out.println( "Node " + data + " found");
}

data = 10;
if (t.SearchBST(root_node5, data) != null) {
System.out.println( "Node " + data + " found");
}
}
}

Output

Node 9 found
Node 7 found

Copyright (c) 2019-2023, Algotree.org.