# Binary Search Trees in C++ – 1 : search function

February 15, 2011 Leave a comment

A binary search tree – BST is a binary tree with the following properties:

1. The data in the left child of a node is <= its own data.

2. The data in the right child of a node is >= its own data.

——-

We can easily see why it is called a binary search tree. Consider what happens if we try to search for a particular data entry. We compare the data entry with the data stored in the root of the BST. If they are equal, we are done. Else, if our target entry is less than the data contained in the root, we know that the target entry, if it exists in the tree, has to exist in the left subtree. Thus, we have eliminated the right subtree from further consideration. Analogous is the case when the target entry is greater than the data stored in the root. Thus, we can see that this is exactly the same as what happens when we try to search for an element in a sorted array using a binary search algorithm. Hence the name BST.

—————-

We first look at a recursive formulation of the search function.

———

**struct Node**

**{ **

**typedef char Item; **

**Item data; **

**Node *left; **

**Node *right; **

**};**

**——**

//** returns null is target is not present; else returns pointer to appropriate node. **

**Node* search (Node *root, const Item& target)**

**{**

**Node *null_ptr = (Node*) 0; **

**if ( ! root ) **

**return null_ptr; **

**if ( root->data == target) **

**return root; **

**else if (root->data < target) **

**return search(root->right, target); **

**else **

**return search (root->left, target); **

**}
**

———-

We now look at a non-recursive version of the search function. The basic idea of searching remains the same — if the target is less than the root’s data, go to the left child, else if it is greater, go to the right.

———

**Node* search (Node *root, const Item& target) **

**{ **

**Node *temp = root, *null_ptr = (Node*) 0; **

**while (true) **

**{ **

**if (temp == (Node*) 0) **

**return null_ptr;
**

**if (temp -> data == target) **

**return temp; **

**else if (target < temp->data) **

**temp = temp->left; **

**else **

**temp = temp -> right;
**

**}**

**}
**

——–

Searching in a BST takes O(log n) time in the average case. In the worst case – if the tree is highly skewed, it takes O(n) time. [n is the number of nodes in the BST.]

—————-