CODEWITHSUNDEEP
data-structuresbinary-tree
AlanSTACK
AlanSTACK

Reputation: 6075

What is min/max depth of a binary tree with n leaf nodes?

I know that the max depth of a binary tree with n nodes is n-1

I know that the max depth of a binary tree with n nodes is floor(log2n)

But what about if I am just given the number of leaf nodes?

Upvotes: 1

Views: 2357

Answers (1)

Edwin Buck
Edwin Buck

Reputation: 70979

There are two ideals in binary trees.

The ideal "deepest" tree.

 *
  *
   *
    *
     a

This tree obviously contains one leaf node, and could have an infinite number of intermediate nodes. This means the maximum depth is unbounded for one leaf node (unless your problem requires internal nodes with more than one child)

The ideal "shallowest" tree 

          *
      *       *
    *   *   *   *
   a a a a a a a a

This tree obviously contains 2^(depth-1) leaves (for trees of depth 1 or greater), and through the magic of math would have a depth of log(base2)(leaves) = depth-1 or 1+log(base2)(leaves). Since we can't have a fractional depth, this must be aligned to ceil(1+log(base2)(leaves))

To test this, let's build a table

leaves formula                        depth
  1    ceil(1+log(base2)(1)) => ceil(1+0) => ceil(1) => 1
  2    ceil(1+log(base2)(2)) => ceil(1+1) => ceil(2) => 2
  3    ceil(1+log(base2)(3)) => ceil(1+1.58) => ceil(2.58) => 3
  4    ceil(1+log(base2)(4)) => ceil(1+2) => ceil(3) => 3
  5    ceil(1+log(base2)(5)) => ceil(1+2.32) => ceil(3.32) => 4

and so on.

So the range of depth for a tree with n nodes (where n > 0) is

[ceil(1+log(base2)(n)), infinity)

unless there are stronger constraints on the deepest tree, like "each internal node must have two siblings (or something like that)"

Upvotes: 1

Related Questions