Course- B.Tech.
Type- Core
Course Code- CSET202 Course Name- Data Structure using C++
Year- 2024 Semester- Odd
Date- 24/9/2024 Batch- 2022-2026
CO-Mapping
CO1 CO2 CO3
Q1 √
Q2 √
Q3 √
Q4 √
Q5 √
Q6 √
Topic:
Tree Traversal, Insertion and Deletion, BST
Objectives
1. Students will be able to learn about various operations on BST and Heap.
2. Students will be able to learn about various applications of BST and Heap.
Tutorial 10 – Binary Search Tree, Heap
Questions:
1. Write an algorithm to check whether the given binary tree is BST or not.
2. Given a BST and a positive integer k, where k ≤ number of elements of the given BST. Write an algorithm
to find the kth-smallest element in the given BST. For example, the 4th smallest node in the following
BST is 15, and the 6th smallest is 20. The 8th smallest node does not exist.
3. Consider the following BST.
Perform following traversals for the given BST.
(a) Pre-order traversal
(b) In-order traversal
(c) post-order traversal
4. Given the pre-order and in-order traversals of a BST. Construct the BST from the given pre-order and
in-order traversals.
Pre-order: 12, 8, 6, 9, 16, 15, 19
In-order: 6, 8, 9, 12, 15, 16, 19
5. Give a recursive algorithm to find the smallest element in a binary search tree.
6. Construct a min binary heap with the following sequence of numbers:
70, 42, 35, 8, 12, 15, 23, 6, 90 (a)
Show the heap at each stage of construction.
(b) Remove the root node from the min binary heap that you have constructed and show the heap after
deletion.
