Google Answers Logo
View Question
 
Q: Graph and Tree Problem ( Answered,   0 Comments )
Question  
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
level).

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
Answer  
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?

-Haversian
Comments  
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 answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


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