Data Structures and Algorithms - Old Questions

3. Define Binary Search Tree (BST). Write an algorithm to insert a node in non-empty BST. Construct BST from the data:

10, 20, 30, 25, 27, 7, 4, 23, 26, 21.

Binary Search Tree

A binary search tree (BST) is a binary tree that is either empty or in which every node contains a key (value) and satisfies the following conditions:

• All keys in the left sub-tree of the root are smaller than the key in the root node
• All keys in the right sub-tree of the root are greater than the key in the root node
•  The left and right sub-trees of the root are again binary search trees

Example:

Given the following sequence of numbers,

        14, 4, 15, 3, 9, 14, 18

The following binary search tree can be constructed:

Algorithm to insert node in non-empty BST

Create a Node with given value and set its left and right to NULL.

insert(struct bnode *root, int item)

{

    if(item < root->info)

         root->left = insert(root->left, item);

    else

         root->right = insert(root->right, item);

    return root;

}

E.g.

Given data

10, 20, 30, 25, 27, 7, 4, 23, 26, 21

Binary Search Tree (BST) for given data is given below: