Let T be a binary tree with n nodes, and let p be the level numbering of

Question:

Let T be a binary tree with n nodes, and let p be the level numbering of the nodes of T, so that the root, r, is numbered as p(r)=1, and a node v has left child numbered 2p(v) and right child numbered 2p(v)+1, if they exist. 

a. Show that, for every node v of T, p(v) ≤ 2(n+1)/2 − 1. 

b. Show an example of a binary tree with at least five nodes that attains the above upper bound on the maximum value of p(v) for some node v.

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For  book-img-for-question

Algorithm Design And Applications

ISBN: 9781118335918

1st Edition

Authors: Michael T. Goodrich, Roberto Tamassia

Question Posted: