Data Structures and Algorithms - Old Questions

2. Describe properties of Binary Search Tree. Write recursive algorithms for constructing BST and its traversals. Illustrate them with an example.

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:

Properties of BST:

• Nodes of the tree are represented in a parent-child relationship
• Each parent node can have zero child nodes or a maximum of two subnodes or subtrees on the left and right sides.
• Every sub-tree, also known as a binary search tree, has sub-branches on the right and left of themselves.
• All the nodes are linked with key-value pairs.
• The keys of the nodes present on the left subtree are smaller than the keys of their parent node
• Similarly, The left subtree nodes' keys have lesser values than their parent node's keys.

Recursive Algorithm for Constructing BST

void insert(struct bnode *root, int item)

{

    if(root=NULL)

    {

        root=(struct bnode*)malloc (sizeof(struct bnode));

        root->left=root->right=NULL;

        root->info=item;

    }

    else

    {

        if(item<root->info)

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

        else

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

    }

}

Recursive Algorithm to traverse BST using preorder traverse method

void preorder(struct bnode *root)

{

    if(root!=NULL)

    {

    printf(“%c”, root->info);

    preorder(root->left);

    preorder(root->right);

    }

}