CODEWITHSUNDEEP
binary-treemaxmindepthformulas
Lemex
Lemex

Reputation: 3794

Balanced Binary Trees Depth

When given a number of nodes we are able to calculate the min depth of the binary tree by doing log2(n)

Where n is the number of nodes.

If you draw the tree out for the maximum depth for example 12 nodes you work out that the maximum depth can only be 4 if the tree is to remained balanced.

                0
               /   \
              0     0
            /  \   / \
           0    0 0   0
          /\     \     \ 
        0   0      0    0

Sorry for the bad ascii art. Does anyone know of a forumla that is able to calculate the max depth of a binary tree when given the number of nodes? Or at least point me in the right direction?

Upvotes: 1

Views: 8874

Answers (3)

user2366458
user2366458

Reputation: 21

The simplest answer looks like this:

int getMaxDepth(Node node)
{
    if(node == null) {
        return 0;
    }

    int leftDepth = 1 + getMaxDepth(node.left);
    int rightDepth = 1 + getMaxDepth(node.right);

    return left > right ? left : right;
}

The concept explained

Upvotes: 2

MANOJ KUMAR SAHOO
MANOJ KUMAR SAHOO

Reputation: 11

Let no of nodes given(n)=15 Formula is- log2n (log n base 2) now take a max value which must be less than 15 and must be a power result of 2. As here 15 is given the no will be 8. Now, n=8 log2(8)= 3 ,which is our required answer

Upvotes: 1

Dr.Kameleon
Dr.Kameleon

Reputation: 22810

By using the root element :

int maxHeight(BinaryTree *p) {
  if (!p) return 0;
  int left_height = maxHeight(p->left);
  int right_height = maxHeight(p->right);
  return (left_height > right_height) ? left_height + 1 : right_height + 1;
}

By using the number of nodes and some math logic (which I definitely cannot express properly (I'm by no means a math guru); but here it is) :

Observation :

  • 2-3 nodes => maxDepth = 1 (2 = 2^1, 3 = 2^1,.. < 2^2 )
  • 4-7 nodes => maxDepth = 2 (4 = 2^2, 5 = 2^2,.., 6 = 2^2,.., 7 = 2^2,... < 2^3)
  • 8-15 nodes => maxDepth = 3
  • ...

Analysis :

  • m => max Depth (actual the INT part of the depth, discard any decimal places)

  • n => number of nodes

  • ln => natural logarithm (=log[e])

  • 2^m = n

  • ln(2^m) = ln(n)

  • m*ln(2) = ln(n)
  • m = ln(n)/ln(2)

Conclusion :

Now, if m = 2,... , then the maximum depth is 2. Just get the int part of it. ;-)

NOTE: I'm definitely re-inventing the wheel here; but that's probably part of the fun of dealing with something you know nothing about; and doing it, solely following your instinct and observations... :-)

Upvotes: 3

Related Questions