Register

ISRO2016-30

9,172 views
5 votes
5 votes

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

  1. $\log_{2}n$ nodes
  2. $n+1$ nodes
  3. $2n$ nodes
  4. $2n+1$ nodes
User Avatar

3 Answers

Best answer
22 votes
22 votes
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$.
• selected by
User Avatar
5 votes
5 votes
option D:

2n + 1 nodes in total
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

33 votes
33 votes
4 answers
1
Kathleen asked Sep 21, 2014
16,573 views
GATE CSE 2007 | Question: 38, ISRO2016-27
The following postfix expression with single digit operands is evaluated using a stack: $8 \ 2 \ 3 \ {}^\hat{} ∕ \ 2 \ 3 * + 5 \ 1 * -$ Note that $^\hat{}$ is the exponentiation operator. The top two elements of the stack after the first $*$ is evaluated are $6, 1$ $5, 7$ $3, 2$ $1, 5$
The following postfix expression with single digit operands is evaluated using a stack:$$8 \ 2 \ 3 \ {}^\hat{} ∕ \ 2 \ 3 * + 5 \ 1 * -$$Note that $^\hat{}$ is the ex...
User Avatar
39 votes
39 votes
8 answers
2
Kathleen asked Sep 15, 2014
18,708 views
GATE CSE 2002 | Question: 1.25, ISRO2008-30, ISRO2016-6
The maximum number of edges in a $n$-node undirected graph without self loops is $n^2$ $\frac{n(n-1)}{2}$ $n-1$ $\frac{(n+1)(n)}{2}$
The maximum number of edges in a $n$-node undirected graph without self loops is$n^2$$\frac{n(n-1)}{2}$$n-1$$\frac{(n+1)(n)}{2}$
User Avatar
64 votes
64 votes
15 answers
3
Arjun asked Jul 6, 2016
37,136 views
GATE CSE 2007 | Question: 15, ISRO2016-26
Consider the following segment of C-code: int j, n; j = 1; while (j <= n) j = j * 2; The number of comparisons made in the execution of the loop for any $n > 0$ is: $\lceil \log_2n \rceil +1$ $n$ $\lceil \log_2n \rceil$ $\lfloor \log_2n \rfloor +1$
Consider the following segment of C-code:int j, n; j = 1; while (j <= n) j = j * 2;The number of comparisons made in the execution of the loop for any $n 0$ is:$\lceil \...
User Avatar
8 votes
8 votes
2 answers
4
Arjun asked Jul 6, 2016
3,902 views
ISRO2016-43
A simple two-pass assembler does which of the following in the first pass: Checks to see if the instructions are legal in the current assembly mode It allocates space for the literals. It builds the symbol table for the symbols and their values. All of these
A simple two-pass assembler does which of the following in the first pass:Checks to see if the instructions are legal in the current assembly modeIt allocates space for t...
User Avatar
Link Copied!