A complete binary tree with N nodes has depth approximately equal to
A) 2N
B) log N
C) N2
D) N

Question

Quizplus · Accepted Answer

In a complete binary tree, all levels except possibly the last are completely filled, and all nodes are as far left as possible. Therefore, the maximum number of nodes at depth d is 2^d. The minimum number of nodes in a binary tree of depth d is 2^d. The maximum number of nodes in a binary tree of depth d is (2^(d+1))-1. These can be used to find the approximate depth of a complete binary tree with N nodes. By taking the logarithm base 2 of N, we get the approximate depth of the tree. Therefore, the answer is B, log N.

A Complete Binary Tree with N Nodes Has Depth Approximately