For a binary tree with n nodes, how many nodes are there which has got both a parent and a child?

Interview Candidate
Jun 26th, 2005
3
3554

First
Prev
Next
Last

Showing Answers 1 - 3 of 3 Answers

Subrata Nath

May 9th, 2006

Ans -
There are total n nodes . Here out of the n nodes except the leaves and root ,all the others have both the child and parent . Let us assume that the heigh of the binary tree is h.
Then h = log n ( Base 2) .[ floor value ] .
No of leaves = 2^log n (base 2 ).
Hence the no of nodes having both the parent and child is =
n-2^log n (base 2 ) -1