131

Searching

Searching means finding or locating some specific element or node within a data structure. However, searching for some specific node in binary search tree is pretty easy due to the fact that, element in BST are stored in a particular order.

1. Compare the element with the root of the tree.
2. If the item is matched then return the location of the node.
3. Otherwise check if item is less than the element present on root, if so then move to the left sub-tree.
4. If not, then move to the right sub-tree.
5. Repeat this procedure recursively until match found.
6. If element is not found then return NULL.

Algorithm:

Search (ROOT, ITEM)

• Step 1: IF ROOT -> DATA = ITEM OR ROOT = NULL
      Return ROOT
     ELSE
     IF ROOT < ROOT -> DATA
     Return search(ROOT -> LEFT, ITEM)
    ELSE
     Return search(ROOT -> RIGHT,ITEM)
    [END OF IF]
    [END OF IF]
• Step 2: END