 View Question 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``` ```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```  