Lab Assignment 8
Binary Search Trees
1. Write program using functions for binary tree traversals: Pre-order, In-order and Post-
order using recursive approach.
2. Implement following functions for Binary Search Trees
(a) Search a given item (Recursive & Non-Recursive)
(b) Maximum element of the BST
(c) Minimum element of the BST
(d) In-order successor of a given node the BST
(e) In-order predecessor of a given node the BST
3. Write a program for binary search tree (BST) having functions for the following
operations:
(a) Insert an element (no duplicates are allowed),
(b) Delete an existing element,
(c) Maximum depth of BST
(d) Minimum depth of
4. Write a program to determine whether a given binary tree is a BST or not.
Practice questions
5. Write a non-recursive function to traverse a BST in in-order traversal using stack.
6. Given preorder and in-order traversals, write a program to construct the Binary Tree.
7. Given in-order and post-order traversals, write a program to construct the Binary Tree.
8. Write a program to merge two BSTs into a doubly-linked list in sorted order.
Example Input:
20
T1 / \
10 30
/ \
25 100
50
T2 / \
5 70
Output:
5 <—> 10 <—> 20 <—> 25 <—> 30 <—> 50 <—> 70 <—> 100 <—> null
