ISRO2016-30

Question

A complete binary tree with $n$ non-leaf nodes contains

• A. $\log_{2}n$ nodes
• B. $n+1$ nodes
• C. $2n$ nodes
• D. $2n+1$ nodes

Comments

ManojK I think this question can't be answered unless you define what exactly do you mean by complete binary tree .you must have a proper definition for complete binary tree and in gate i guess they don't ask such question without there own definition what do they mean by the complete binary tree  otherwise answer will be many or none

Answer 1

A complete binary tree is one in which all levels except those in last level are fully filled and even in last level all nodes are filled from left to right.

Now, a tree is a graph and we can consider the binary tree as an undirected graph also. So, degree of root = 2, degree of all internal nodes excluding root = 3 (one parent and 2 child nodes) and degree of leaf nodes = 1 (only parent). (Assuming root is not a leaf and tree is full also).

Now, sum of degrees in a graph $=2e$, where $e$ is the no. of edges.

In a tree we have $e = x-1$ where $x$ is the total no. of nodes. Now, we have $n$ non-leaf nodes, so that means $x - n $ leaf nodes and $n-1$ internal nodes excluding root. So, equating the sum of degrees, we can write

$2 + 3.(n-1) + x - n  = 2.(x - 1) \\ \implies x = 2n + 1$.

Now, if tree is complete but not full, the last node might have no sibling and thus total number of nodes can be $2n$ also (one internal node having degree $2$ instead of $3$.

Answer 2

option D:

2n + 1 nodes in total

Comments

yes of course answer to this question can be 2n as well as 2n+1,

this is complete binary tree ,

but if F had second child, that is complete binary tree too

---

its a elimination method in which you took a tree and eliminate the options I am asking for a mathematical  proof or a general method that can be applied in all the case's not just like answer can be (2n or 2n+1) .be this or that.

---

@shekhar see my answer..

Answer 3

https://gateoverflow.in/55672/isro2016-30