WorksheetsDAY 29 Binary Search Trees & AVL Tree- 18th July 2024
Total questions: 20
Worksheet time: 10mins
Which of the following properties does a Binary Search Tree (BST) satisfy?
Each node has at most two children.
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
All of the above
What is the time complexity of searching for an element in a balanced Binary Search Tree?
O(1)
O(log n)
O(n)
O(n log n)
What is the in order traversal of the BST shown below? 4 2 1 3 6 5 7
4 2 1 3 6 5 7
1 2 3 4 5 6 7
7 6 5 4 3 2 1
4 2 3 1 6 5 7
Which operation does not necessarily preserve the BST property?
Insertion
Deletion
Searching
None of the above
What is the height of a BST with 7 nodes in its most balanced form?
2
3
4
5
Which of the following algorithms is used for searching in a BST?
Breadth-First Search
Depth-First Search
Binary Search
Linear Search
Which of the following cases can occur when deleting a node from a BST?
The node is a leaf.
The node has one child.
The node has two children.
All of the above
In a BST, the node with the minimum value is found:
At the root
In the leftmost node
In the rightmost node
In the middle node
What is the successor of a node in a BST?
The node with the next higher key
The node with the next lower key
The left child
The right child
What is the worst-case time complexity of inserting a new node in an unbalanced BST?
O(1)
O(log n)
O(n)
O(n log n)
What is an AVL tree?
A tree with all levels filled
A binary tree with an additional balance factor
A tree with a maximum of 3 children per node
A binary tree with height equal to the number of nodes
What is the balance factor of a node in an AVL tree?
Height of left subtree - Height of right subtree
Height of right subtree - Height of left subtree
The number of children
The difference in the number of nodes between the left and right subtrees
An AVL tree is balanced if, for every node in the tree, the balance factor is:
-1, 0, or 1
-2, 0, or 2
-3, 0, or 3
0 only
Which of the following operations may cause an AVL tree to become unbalanced?
Insertion
Deletion
Searching
Both 1 and 2
What is the time complexity of rebalancing an AVL tree?
O(1)
O(log n)
O(n)
O(n log n)
Which rotation is used to balance an AVL tree when a node is inserted into the right subtree of the right child?
Left Rotation
Right Rotation
Left-Right Rotation
Right-Left Rotation
In an AVL tree, what type of rotation is performed when a node is inserted into the left subtree of the right child?
Left Rotation
Right Rotation
Left-Right Rotation
Right-Left Rotation
After performing an insertion in an AVL tree, the balance factor of a node becomes -2. This implies:
The left subtree is higher by 2 levels.
The right subtree is higher by 2 levels.
The tree is perfectly balanced.
None of the above
What type of tree traversal is often used to print the elements of an AVL tree in sorted order?
Preorder
Inorder
Postorder
Level Order
In an AVL tree, which of the following properties is true for every node?
Each node has exactly two children.
The tree is perfectly balanced.
The height difference between the left and right subtrees of any node is at most 1.
The tree cannot be empty.
