Scribd
Upload
18 views

Dds Assignment 3

Dds Assignment 3

Uploaded by

Among Us
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
18 views

Dds Assignment 3

Dds Assignment 3

Uploaded by

Among Us
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

303105201 - Design of Data Structures

Academic Year - 2024-2025 – Sem-3


ASSIGNEMNT-3
(Based on Unit-5 & 6)
Submission Date – Latest by 20-September-2024
Long Questions: -
SR.No Question
Define binary search tree and generate a BST tree for following data.
1.
10,8,9,30,20,50,40,3
Given Inorder and Preorder traversal, Generate tree and find Postorder traversal
2.
Inorder traversal = {4, 2, 5, 1, 3, 6}
Preorder traversal = {1, 2, 4, 5, 3, 6}
The post-order and Inorder traversal of binary search tree is:
3.
post-order: 5, 10, 35, 30, 40, 25, 55, 65, 70, 60, 50.
Inorder:5,10,25,30,35,40,50,55,60,65,70.
Construct a binary search tree and find the pre-order traversal of the BST.
Generate a binary search tree for following numbers and perform in-order and post-order
4.
traversals: 50, 40, 80, 20, 0, 30, 10, 90, 60, 70
What is a drawback of BST? How we can overcome that? Construct the AVL search tree by inserting
5.
the following elements in the order of their occurrence: 64, 1, 44, 26, 13, 110, 98, 85
Write a short note on AVL tree. Explain any two rotation techniques
6.
Construct AVL tree for following data: 10,20,30,40,50,60,70,80
7.
Explain AVL tree with the help of an example also show insertion and deletion with the help of an
8.
example.

Short Questions.
SR.No Question
1. Define: Height of a tree.
2. What is common in inorder, preorder and postorder traversal?
3. The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum
number of nodes in a binary tree of height n are?
4. The in-order traversing of binary search tree is always in _____________ order.
5. A Binary tree has 30 leaves. How many number of nodes will be there in tree having two children?
(a) 28 (c) 31
(b) 32 (d) 29
6. Total no of nodes in the binary tree of having height h.
7. What is the height of an AVL tree with n nodes?
8. What is the time complexity of searching in an AVL tree?
9. What triggers a double rotation in an AVL tree?
10. What are the four types of rotations used in AVL trees?
11. Why is balancing important in an AVL tree?
MCQ Questions:
1. What is the height of a tree with only one node?

a) 0 b) 1 c) -1 d) 2

2. Which of the following traversals would give the elements of a binary search tree in sorted order?

A) Preorder B) Inorder C) Postorder D) Level-order.

3. Which of the following is not a type of binary tree?

A) Full Binary Tree B) Complete Binary Tree

C) Degenerate (or Pathological) Tree D) B-Tree

4. Which of the following statements is true about threaded binary trees?

A) They are always balanced.


B) They have additional links to facilitate faster traversal.
C) They are used primarily for priority queues.
D) They have more nodes than a regular binary tree.

5. Which traversal technique can be performed efficiently on a threaded binary tree without recursion or a
stack?

A) Preorder traversal
B) Inorder traversal
C) Postorder traversal
D) Level-order traversal

You might also like