Which of the following is incorrect with respect to binary trees?

Category: QuestionsWhich of the following is incorrect with respect to binary trees?
Editor">Editor Staff asked 5 months ago

Which of the following is incorrect with respect to binary trees?
 
(a) Let T be a binary tree. For every k ≥ 0, there are no more than 2k nodes in level k
 
(b) Let T be a binary tree with λ levels. Then T has no more than 2^λ – 1 nodes
 
(c) Let T be a binary tree with N nodes. Then the number of levels is at least ceil(log (N + 1))
 
(d) Let T be a binary tree with N nodes. Then the number of levels is at least floor(log (N + 1))
 
I want to ask this question from Binary Tree Properties in chapter Binary Trees of Data Structures & Algorithms I
 
The question was asked in semester exam.

1 Answers
Editor">Editor Staff answered 5 months ago

The correct option is (d) Let T be a binary tree with N nodes. Then the number of levels is at least floor(log (N + 1))
 
To explain: In a binary tree, there are atmost 2k nodes in level k and 2^k-1 total number of nodes. Number of levels is at least ceil(log(N+1)).


Notice: Trying to get property 'ID' of non-object in /home/fvckxqmi/public_html/wp-content/themes/blocksy/inc/single/single-helpers.php on line 17

Notice: Trying to get property 'ID' of non-object in /home/fvckxqmi/public_html/wp-content/themes/blocksy/inc/single/single-helpers.php on line 17

Notice: Trying to get property 'ID' of non-object in /home/fvckxqmi/public_html/wp-content/themes/blocksy/inc/single/single-helpers.php on line 17

Notice: Trying to get property 'ID' of non-object in /home/fvckxqmi/public_html/wp-content/themes/blocksy/inc/single/single-helpers.php on line 17
Articles: 40701