Binary Search Tree: A Non-Linear Data Structure

Definition: A binary search tree is a binary tree.  It may be empty.  If it is not empty, it satisfies the following properties:
1. Every element has a key, and no two elements have the same key, that is, the keys are unique.
2. The keys in a nonempty left subtree must be smaller than the key in the root of the subtree.
3. The keys in a nonempty right subtree must be larger than the key in the root of the subtree.
4. The left and right sub-trees are also binary search trees.

Example of the Binary Search Tree:

Searching operation performed on Binary Search Tree:
Suppose we wish to search for an element with a key.  We begin at the root.  If the root is NULL, the search tree contains no elements and the search is unsuccessful.  Otherwise, we compare key with the key value in root.  If key equals root’s key value, then the search terminates successfully.  If key is less than root’s key value, then no elements in the right sub-tree can have a key value equal to key.  Therefore, we search the left sub-tree of root.  If key is larger than root’s key value, we search the right sub-tree of root.

Implementation of Recursive function for Binary Search Tree:
tree_ptr   search( tree_ptr   root, int   key ) 
if ( !=root )
return   NULL;
if ( key = = root->data )
return   root;
if ( key < root->data )

return   search ( root->left_child, key );
return   search ( root->right_child, key );

Mukesh Rajput
Mukesh Rajput

Mukesh Rajput

I am a Computer Engineer, a small amount of the programming tips as it’s my hobby, I love to travel and meet people so little about travel, a fashion lover and love to eat food, I am investing a good time to keep the body fit so little about fitness also..

Post A Comment:


Mukesh Rajput