What is a balanced binary search tree?
a) A binary search tree where the height of the left and right subtrees differ by no more than one
b) A tree where all leaves are at the same level
c) A binary tree with equal numbers of left and right children
d) A tree where all nodes have the same value
Answer:
a) A binary search tree where the height of the left and right subtrees differ by no more than one
Explanation:
A balanced binary search tree is a binary search tree where the height of the left and right subtrees of every node differ by no more than one. This ensures that the tree remains balanced, leading to logarithmic time complexity O(log n) for search, insertion, and deletion operations.
Examples of balanced binary search trees include AVL trees and Red-Black trees, which use various balancing techniques to maintain this height property.
Balanced trees are crucial in maintaining the efficiency of operations in scenarios where the tree can become skewed, such as in databases and search algorithms.
Reference:
DSA (Data Structures and Algorithms) MCQ Questions and Answers