Roman C. answered • 04/01/16

Tutor

4.9
(647)
Masters of Education Graduate with Mathematics Expertise

The maximum number of nodes in a depth d binary tree is 2

^{d+1}- 1, which happens for a full tree. Take the inverse of this to get the answer.2

^{d+1}- 1 = nd = log

_{2}(n + 1) - 1More precisely, we must take the ceiling, since we can't have a fractional depth. Thus the minimum depth of a tree with n nodes is

d = ⌈ log

_{2}(n+1) ⌉ - 1For 5 nodes we get a minimum depth of

d = ⌈log

_{2}6⌉ - 1 = ⌈2.58...⌉ - 1 = 3 - 1 = 2Roman C.

tutor

The root node is considered as being at depth 0 by most standards. So we can make a depth 3 tree with 15 nodes. It would be a full tree with 1,2,4,8 nodes at depths 0,1,2,3 respectively.

Report

04/02/16

Justin w.

_{2}(16)⌉ - 1 => ⌈4⌉ -1=> 4-1 =3 Right!04/02/16