Algotree > Algorithms > Tree & Graph Traversal > Binary Search Tree > Searching A Node In Binary Search Tree

Searching A Node In Binary Search Tree

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.