In a complete binary tree with n nodes, which expression best approximates the…

Concept

In a rooted tree, the distance between two nodes is the number of edges on their unique path. If their depths are d1 and d2 and their lowest common ancestor has depth a, then their distance is d1 + d2 − 2a.

A complete binary tree with n nodes has height h = ⌊log2 n⌋, where height is the greatest root-to-node distance in edges. Therefore, any node-to-node path has at most 2h edges.

Application

1. Let h = ⌊log2 n⌋.

2. Choose deep leaves in the two root subtrees. Their lowest common ancestor is the root, so their path length is the sum of their depths.

3. Those depths are h or h − 1 in a complete tree, so the diameter is 2h up to a small additive constant.

4. Substituting h gives a distance of approximately 2 log2 n edges.

Cross-check

For a perfect binary tree, n = 2h+1 − 1 and two opposite deepest leaves are exactly 2h edges apart. Since h = log2(n+1) − 1, this distance equals 2 log2(n+1) − 2, confirming the approximation 2 log2 n.

Result: The maximum distance is best approximated by 2 log2 n.