TREE DS

Question

The number of nodes of degree one in a complete binary tree of 2$^{30}$ nodes is?

(1) 2$^{29}$ +1

(2) 2$^{29}$

(3) 2$^{30}$

(4) 1

Comments

@srestha

no no, actually here degree refers to the number of children the node has. That means all leafs node have degree 0.

---

@srestha mam ,please look carefully ....there is a question mark 😂. I have not seen this question after that.

the answer should be 2^29.

2^30  represents a tree having height =30 where root node starts from height=0. and there will be only 1 leaf node at height 30.

for a complete binary tree,

leaf nodes = internal nodes*(d-1) +1    (here d=degree=2)

=> leaf nodes -internal nodes = 1

=> leaf nodes + internal nodes = 2^30 (given)

adding both equations,

2*leaf nodes = 2^30 + 1

=>leaf nodes = 2^29 +0.5

=> leaf nodes = 2^29 ( since 0.5 node is not possible)

 

 

 

---

@Satbir

I also finding this

yes $2^{29}$ correct here 

but not correct all the time, because complete binary tree maynot have all leaf node at same level