In a balanced binary search tree, the height grows as a function of n?

In a balanced binary search tree, the height grows as a function of n?

• A. O(log n)
• B. O(n)
• C. O(1)
• D. O(n log n)

Answer: (A)

In a balanced binary search tree, each level can hold about twice as many nodes as the previous level, so the total number of nodes n that can be accommodated with height h is roughly 2^h. Solving 2^h ≈ n gives h ≈ log2(n). Since Big-O ignores the base of the logarithm, the height grows as O(log n). This is why operations that depend on height, like search, stay efficient in a balanced BST. The other options would imply unrealistic growth for a balanced tree: linear height O(n) would mean a chain of nodes, which isn’t balanced; constant height O(1) cannot accommodate more nodes as n grows; and O(n log n) grows faster than the actual height.

In a balanced binary search tree, each level can hold about twice as many nodes as the previous level, so the total number of nodes n that can be accommodated with height h is roughly 2^h. Solving 2^h ≈ n gives h ≈ log2(n). Since Big-O ignores the base of the logarithm, the height grows as O(log n). This is why operations that depend on height, like search, stay efficient in a balanced BST.

The other options would imply unrealistic growth for a balanced tree: linear height O(n) would mean a chain of nodes, which isn’t balanced; constant height O(1) cannot accommodate more nodes as n grows; and O(n log n) grows faster than the actual height.