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

This content is provided for educational purposes. Feel free to learn, practice, and share knowledge.
For questions or contributions, visit algotree.org

"Without requirements or design, programming is the art of adding bugs to an empty text file. - Louis Srygley"