Binary Trees, Binary Search Trees (BST), and AVL Trees are fundamental data structures in computer science that serve various purposes. From general hierarchical data representation to efficient searching and balancing operations, these trees play an integral role in algorithm design and database applications. Let’s test your knowledge with these 15 Multiple Choice Questions.
1. Which of the following trees allows nodes with a maximum of two children?
Answer:
Explanation:
By definition, a binary tree is a tree data structure in which each node has at most two children.
2. In a Binary Search Tree (BST), left child nodes contain values which are:
Answer:
Explanation:
In a BST, the left child node always contains a value lesser than its parent node, and the right child contains a value greater than its parent node.
3. What is the maximum number of nodes in a binary tree of height ‘h’?
Answer:
Explanation:
A binary tree of height ‘h’ has a maximum of 2^h – 1 nodes.
4. Which tree ensures that the height difference between the left and right child of any node is at most 1?
Answer:
Explanation:
AVL Trees are self-balancing binary search trees where the height difference (balance factor) between the left and right subtree for any node is no more than 1.
5. In a BST, which traversal will yield a sorted order of its elements?
Answer:
Explanation:
Inorder traversal of a BST will give nodes in non-decreasing order.
6. Which tree data structure is named after its inventors Adelson-Velsky and Landis?
Answer:
Explanation:
AVL Tree is named after its inventors Adelson-Velsky and Landis.
7. If a binary tree is both full and complete, it is also a:
Answer:
Explanation:
A binary tree is perfect if all its levels are fully populated, which implies the tree is both full and complete.
8. What is the worst-case height of an AVL tree with ‘n’ nodes?
Answer:
Explanation:
The height of an AVL tree is bounded by 1.44 log(n).
9. In a BST, the ___ typically contains values greater than its parent.
Answer:
Explanation:
In a BST, the right child node always contains a value greater than its parent node.
10. A binary tree where every node has either 0 or 2 children is called:
Answer:
Explanation:
In a full binary tree, every node has either 0 or 2 children.
11. A degenerate (or pathological) tree is a tree where each parent node has:
Answer:
Explanation:
A degenerate tree is essentially a linked list where each parent has only one child.
12. Which tree rotation is used to balance the AVL tree when the left subtree of the left child is causing an imbalance?
Answer:
Explanation:
The Left-Left (LL) rotation is used to balance the mentioned imbalance in an AVL tree.
13. If the height of the binary tree is minimum, it is called a:
Answer:
Explanation:
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as left as possible.
14. Which of the following is not a balanced binary search tree?
Answer:
Explanation:
A standard Binary Search Tree (BST) doesn’t ensure balance. AVL, Red-Black, and Splay are all types of balanced binary search trees.
15. Which tree data structure is useful for database storage systems where balance is maintained by ensuring that a certain number of elements is between the two children?
Answer:
Explanation:
B-Trees are commonly used in databases and filesystems due to their ability to handle large amounts of data and ensure balance by maintaining a certain number of elements between its children.