UNIT IV
Course University
[Link]. Question Outcome Question
1. Define a tree in data structures. CO 3
2. State the properties of a binary tree CO 3
3. Define Binary Tree CO 3
4. What is the difference between a full binary tree and a complete binary tree? CO 3
5. Define AVL tree and state its properties. CO 3
6. What is a Binary Search Tree (BST)? CO 3
If the depth of the binary tree is k, the maximum number of nodes in the
7. binary tree is 2k^-1. Justify CO 3
8. Compare the preorder, inorder, and postorder traversals CO 3
9. Construct a max heap with the following data 20,1,2,40,30 CO 3
10. What are the applications of heaps? CO 3
11. Define a multi-way search tree CO 3
12. What is the degree of a node in a tree? CO 3
13. Illustrate the steps in the construction of a heap of records with the following CO 3
key values: 12, 33, 67, 8, 7, 80, 5, 23
14. Find the topological ordering of the following graph CO 3
15. What are the categories of AVL rotations? CO 3
16. CO 3
17. CO 3
18. CO 3
19. CO 3
20. CO 3
21. CO 3
PART B
Explain the different tree traversal techniques With suitable algorithms and
1. examples CO 3
Draw the binary tree representation of the following arithmetic expression:
2. (((5+2)*(2-1))/((2+9)+((7-2)-1))*8 CO 3
Write the following routines to implement the basic binary search tree
3. operations (i) Perform Insertion and deletion (ii) Perform Search operation CO 3
in Binary Search Tree (iii) Find_min and Find_max
Create a Binary search tree using the following data elements
4. 40,35,58,15,73,31,5,85,51,68,79. CO 3
Construct an expression tree for the expression (a+b*c)+((d*e+1)*g. Give
5. the outputs when you apply an algorithm for preorder, inorder and postorder CO 3
traversal of a binary tree
Insert the following elements in sequence into an empty AVL Tree
6. 43,7,15,24,12,85,74,53 CO 3
i)What are AVL trees?
7. ii) Insert the following elements step by step in sequence into an empty AVL CO 3
tree 63, 9, 19, 27, 18, 108, 99, 81.
Explain the max heap and min heap with insertion and deletion operations in
8. detail CO 3
Construct B Tree of order m=5 for the following keys 1, 12, 8, 2,25, 5, 14,
9. 28, 17, 7, 52, 16, 48, 68, 3, 26, 29, 53, 55, 45 ii) Delete the keys 8 and 55. CO 3
State the rules for deletion.
10. Compare the AVL trees, heaps, and B-Trees in terms of structure and usage CO 3
11. Discuss the real-world applications of tree structures in database indexing CO 3
and file systems
12. Explain the general types of rotations (single and double) used in an AVL CO 3
tree to restore balance during insertion.
13. Demonstrate the rotations that occur when the following sequence of CO 3
elements is inserted into an empty AVL tree: 5, 6, 8, 3, 2, 4, 7
14. Explain how NULL pointers are removed in a binary tree during traversal or CO 3
manipulation.
Write pseudo code for the following binary tree traversal methods:
15. • In-order traversal
CO 3
• Pre-order traversal
• Post-order traversal
16. Create a binary search tree and find the position of element 29 using binary CO 3
search method in an array “A‟ given below : A = {11, 5, 21, 3, 29, 17,2, 43}