# 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.

C++ : Program for searching a node in a BST

``````#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.
``````