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.

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