The height of n elements 2-3 tree is ______

Correct Answer (Detailed Explanation is Below)

B. between log3(n + 1) and log2(n + 1)

Detailed Explanation

A 2-3 Tree is a balanced search tree where:

• Each internal node has either:

  • 2 children (2-node), or

  • 3 children (3-node).

• All leaves are at the same level (perfectly balanced).

Height Analysis:

• Minimum height occurs when all nodes are 3-nodes
  → Maximum branching
  → Height ≈ log₃(n + 1)

• Maximum height occurs when all nodes are 2-nodes
  → Minimum branching
  → Height ≈ log₂(n + 1)

Therefore:

Height of 2-3 tree lies:

$$\textbf{between } \log_3(n + 1) \textbf{ and } \log_2(n + 1)$$