Homework answers / question archive / a) A complete binary tree is defined by a binary tree that all the nodes are filled from top to bottom, left to right

a) A complete binary tree is defined by a binary tree that all the nodes are filled from top to bottom, left to right

Computer Science

Share With

a) A complete binary tree is defined by a binary tree that all the nodes are filled from top to bottom, left to right. Use mathematical induction to prove:

For the number of nodes N, the height of the complete binary tree, h, satisfies :

--> 2^(h−1) ≤ N ≤ 2^h − 1

b) The height h of a complete binary tree with N nodes is ⌊log2 N⌋ + 1. You may use the result from the above.