Searching in a BST

Procedure :
Start from the root node.
Compare the data in each node with the key. If it matches, return pointer to that node.
If the key is lesser than the data in the node, move pointer to the left child.
If the key is greater than the data in the node,  move pointer to the right child.
If pointer becomes null, it means the we have reached the end of the tree and the element was not found. Therefore, return NULL.
Iterative Function :
struct Node *BSTsearch(struct Node *ptr, int key) {
​
    while (ptr != NULL) {
        if (key == ptr -> data) {
            return ptr;
        } else if (key < ptr -> data) {
            ptr = ptr -> left;
        } else {
            ptr = ptr -> right;
        }
    }
    return NULL;
    
}
Recursive Function :
struct Node *BSTsearch(struct Node *ptr, int key) {
​
    if (ptr == NULL) {
        return NULL;
    }
    
    if (key == ptr -> data) {
        return ptr;
    } else if (key < ptr -> data) {
        return BSTsearch(ptr -> left, key);
    } else {
        return BSTsearch(ptr -> right, key);
    }
​
}
Time Complexity : O(log n)
Contributed by Nitin Ranganath

Last modified 3yr ago