Google Answers Logo
View Question
Q: Graph and Tree Problem ( Answered,   0 Comments )
Subject: Graph and Tree Problem
Category: Computers > Graphics
Asked by: math01-ga
List Price: $4.00
Posted: 17 Nov 2002 10:00 PST
Expires: 17 Dec 2002 10:00 PST
Question ID: 109372
2. Consider a complete d-ary tree with height h, that is, a tree where
the root is at level 0, leaves are at height h, and all internal nodes
have d children (i.e, every level in the tree is full except the last

a. What is the upper bound on the numbers of leaves in such a tree? 

b. Find lower and upper bounds for the total number of nodes
Subject: Re: Graph and Tree Problem
Answered By: haversian-ga on 17 Nov 2002 23:12 PST
Consider as a special case a 3-ary tree.  The first few levels look
like this:
                       o          Level 0
                     / | \
                    /  |  \
                   o   o   o      Level 1
                  /|\ /|\ /|\
                  ooo ooo ooo     Level 2

As you can see, the first level contains 1 node.  The second level
contains 3 nodes.  The third level contains 9 nodes.  The pattern
continues.  For a d-ary tree, the nth level contains d^n nodes. 
Therefore, the first through nth level contain d^0 + d^1 + d^2 + . . .
+ d^n nodes.

With that background, on to your questions:

a)   Level h contains at most d^h nodes.  If h is the height, these
nodes are leaves.

b)   With height h, we know there are h-1 fully-populated levels. 
Level h must have at least one node and may have at most d^h nodes. 
So, the lower bound on the total number of nodes is d^0 + d^1 + d^2 +
. . . + d^(h-1) + 1; the upper bound is d^0 + d^1 + d^2 + . . . +
d^(h-1) + d^h.

Does that make sense with the picture drawn out?

There are no comments at this time.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  

Google Home - Answers FAQ - Terms of Service - Privacy Policy