AVL Trees MCQs

By: Prof. Dr. Fazal Rehman Shamil | Last updated: September 20, 2024

What is an AVL tree?

a) A tree where each node has at most two children
b) A self-balancing binary search tree with a balance factor
c) A tree where the left subtree is greater than the root and the right subtree is less than the root
d) A tree where the left subtree is less than the root and the right subtree is greater than the root
Answer: b) A self-balancing binary search tree with a balance factor
In an AVL tree, what is the maximum allowed height difference (balance factor) between the left and right subtrees of any node?

a) 0
b) 1
c) 2
d) 3
Answer: b) 1
What is the worst-case time complexity for searching an element in an AVL tree with
𝑛
n nodes?

a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
Answer: b) O(log n)
Which operation in an AVL tree may require tree rotations to maintain balance?

a) Insertion
b) Deletion
c) Searching
d) Traversal
Answer: a) Insertion

In an AVL tree, which rotation is used to restore balance when the tree becomes right-heavy?

a) Left rotation
b) Right rotation
c) Double left rotation
d) Double right rotation
Answer: a) Left rotation
Which of the following properties is NOT necessarily true for AVL trees?

a) Binary search property
b) Balanced height
c) Complete binary structure
d) Symmetric nodes
Answer: c) Complete binary structure
What is the time complexity of inserting an element into an AVL tree?

a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
Answer: b) O(log n)
Which traversal of an AVL tree visits nodes in non-decreasing order of their values?

a) Preorder
b) Inorder
c) Postorder
d) Level order
Answer: b) Inorder
In an AVL tree, which operation is used to find the successor of a given node?

a) findSuccessor()
b) successor()
c) next()
d) nextNode()
Answer: b) successor()
Which rotation operation is used in AVL trees to restore balance after a double rotation is performed?

a) Left rotation
b) Right rotation
c) Double left rotation
d) Double right rotation
Answer: b) Right rotation
What is the worst-case time complexity for deleting an element from an AVL tree?

a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
Answer: b) O(log n)
In an AVL tree, what is the minimum number of nodes at level
𝑘
k?

a)
2
𝑘
2
k

b)
𝑘
k
c)
𝑘
+
1
k+1
d)
𝑘
−
1
k−1
Answer: a)
2
𝑘
2
k

Which traversal of an AVL tree starts from the root, visits the left subtree, and then visits the right subtree?

a) Preorder
b) Inorder
c) Postorder
d) Level order
Answer: a) Preorder
In an AVL tree, what is the maximum number of edges in a path from the root to a leaf node?

a)
log
⁡
𝑛
logn
b)
𝑛
n
c)
𝑛
n
​

d)
𝑛
−
1
n−1
Answer: d)
𝑛
−
1
n−1
Which rotation operation is used in AVL trees to restore balance after a double left rotation is performed?

a) Left rotation
b) Right rotation
c) Double left rotation
d) Double right rotation
Answer: d) Double right rotation
Which traversal of an AVL tree visits nodes in descending order of their values?

a) Preorder
b) Inorder
c) Postorder
d) Reverse Inorder
Answer: d) Reverse Inorder
In an AVL tree, what is the maximum number of nodes at height
ℎ
h?

a)
2
ℎ
2
h

b)
2
ℎ
+
1
−
1
2
h+1
−1
c)
ℎ
2
h
2

d)
ℎ
h
Answer: a)
2
ℎ
2
h

Which traversal of an AVL tree visits nodes level by level?

a) Preorder
b) Inorder
c) Postorder
d) Level order
Answer: d) Level order
Which of the following statements is true about AVL trees?

a) They are always perfectly balanced.
b) They require no rotations to maintain balance.
c) They guarantee O(1) time complexity for all operations.
d) They maintain a balance factor to ensure heights remain balanced.
Answer: d) They maintain a balance factor to ensure heights remain balanced

 

Data Structures MCQs

Basic Concepts

1. Introduction to Data Structures
   • Abstract Data Types (ADT) MCQs
2. Complexity Analysis MCQs
   • Time complexity MCQs
   • Space complexity MCQs
   • Big O, Big Ω, Big Θ notations MCQs

Linear Data Structures MCQs

1. Arrays MCQs
   • One-dimensional arrays MCQs
   • Multi-dimensional arrays MCQs
   • Operations: traversal, insertion, deletion MCQs
2. Linked Lists MCQs
   • Singly linked list MCQs
   • Doubly linked list MCQs
   • Circular linked list MCQs
3. Stacks MCQs
   • Stack operations (push, pop, peek) MCQs
   • Applications of stacks (expression evaluation, recursion) MCQs
4. Queues MCQs
   • Queue operations (enqueue, dequeue, front, rear) MCQs
   • Types: Simple queue, circular queue, priority queue, deque MCQs

Non-Linear Data Structures MCQs

1. Trees MCQs
   • Binary trees MCQs
   • Binary Search Trees (BST) MCQs
   • AVL Trees MCQs
   • B-trees and B+ trees MCQs
   • Tree traversal methods (in-order, pre-order, post-order) MCQs
2. Heaps MCQs
   • Min-heap MCQs
   • Max-heap MCQs
   • Heap operations (insertion, deletion, heapify) MCQs
   • Applications of heaps (priority queues, heap sort) MCQs
3. Graphs MCQs
   • Graph representation (adjacency matrix, adjacency list) MCQs
   • Graph traversal algorithms (DFS, BFS) MCQs
   • Shortest path algorithms (Dijkstra’s, Bellman-Ford) MCQs
   • Minimum Spanning Tree (Kruskal’s, Prim’s) MCQs

Hashing MCQs MCQs

1. Hash Tables
   • Hash functions MCQs
   • Collision resolution techniques (chaining, open addressing) MCQs
   • Applications of hashing MCQs

Sorting and Searching Algorithms MCQs 

1. Sorting Algorithms MCQs
   • Bubble sort MCQs
   • Selection sort MCQs
   • Insertion sort MCQs
   • Merge sort MCQs
   • Quick sort MCQs
   • Heap sort MCQs
2. Searching Algorithms MCQs
   • Linear search MCQs
   • Binary search MCQs
   • Interpolation search MCQs

Miscellaneous

1. Memory Management in data structures MCQs
   • Dynamic memory allocation MCQs
   • Garbage collection MCQs
2. String Manipulation Algorithms MCQs
   • Pattern matching (KMP, Rabin-Karp) MCQs
   • String hashing MCQs

1. Data Structures MCQs 1
2. Data Structures MCQs 2
3. Data Structures MCQs 3
4. Data Structures MCQs 4
5. Data Structures MCQs 5
6. Stacks Solved MCQs
7. Queues MCQs
8. pointer mcqs
9. Array MCQs