The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
22 views
The number of node in each left subtree is within a factor of $2.$ of the number of nodes in the corresponding right subtree. Also a node allowed to have only one child if that child has no children. This tree has worst case height $O(logn)$. $N$ is the number of nodes in the binary tree.

Is this statement TRUE about Binary Tree?
asked in Algorithms by Veteran (111k points) | 22 views
0
What is the meaning of "The number of node in each left subtree is within a factor of 2.2. of the number of nodes in the corresponding right subtree."?
0
Donot know

They gave solution like this

$N(0)=0$

$N(1)=1$

$N(2)=2$

$N(h)=1+N\left ( h-1 \right )+\frac{1}{2}N\left ( h-1 \right )$

        $=1+\frac{3}{2}N\left ( h-1 \right )$

$N(h)=\Theta \left ( \frac{3}{2} \right )^{h}$

Please log in or register to answer this question.

Related questions

0 votes
1 answer
3
0 votes
0 answers
4
0 votes
0 answers
5
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,532 questions
54,123 answers
187,319 comments
71,044 users