Which of the following trees are height balanced?

A. Binary Search Tree

B. AVL Tree

C. Red-Black Tree

D. B Tree

1. AA and D Only
2. BA, B and D Only
3. CC and D Only
4. DB, C and D Only

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: D. B, C and D Only

Explanation

AVL trees, red-black trees and B-trees all keep their height O(log n). An ordinary binary search tree can degenerate into a chain.