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

Searching A Binary Search Tree

The logic behind searching a node in a binary search tree is as follows:

In a binary search tree, the left child of a parent node is always less than the parent and the right child of a parent is always greater than the parent. Thus we traverse comparing the node to be searched with the root and all the way down the tree till a is found in the tree.

Time complexity of searching a node in a binary search tree with N nodes :
Worst-case time complexity is O(N), if the tree is linear; i.e to search in a binary search tree 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 binary search tree the height would be log N and hence log N comparision before a node is found in the tree.

C++ : Searching a binary search tree. Implemented in C++11

#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)
    {}
};

class Tree {

    public:

    vector<int> order;

    /* The in-order traversal of a valid binary search tree is always in increasing order (sorted) */
    void InOrder(Node * node) {

        if (node != NULL) {
            InOrder(node->left);
            cout << node->data << " ";
            order.push_back(node->data);
            InOrder(node->right);
        }
    }

    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 * root1 = new Node(6);
    root1->left = new Node(4);
    root1->right = new Node(9);

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

    /*   5
        / \
       1   7  
            \
             8  */
    Node * root2 = new Node(5);
    root2->left = new Node(1);
    root2->right = new Node(7);
    root2->right->right = new Node(8);

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

    return 0;
}

Output of validating a binary search tree implemented in C++11

Node 9 found.
Node 7 found.
Node 10 not found.