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.
Answer
AI is thinking...
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);
}
}