edited by
25,855 views
57 votes
57 votes

In a binary tree, the number of internal nodes of degree $1$ is $5$, and the number of internal nodes of degree $2$ is $10$. The number of leaf nodes in the binary tree is

  1. $10$
  2. $11$
  3. $12$
  4. $15$
edited by

11 Answers

Best answer
98 votes
98 votes

A node in a binary tree has degree $0, 1$ or $2$. 

Ref: http://faculty.cs.niu.edu/~mcmahon/CS241/Notes/bintree.html

We are given no. of $1$ degree node $= 5$, no. of $2$ degree nodes $= 10$. 

Total no. of edges $= 1*5 + 2*10 = 25$ (In tree degree is for outgoing edges only, and hence each degree corresponds to an edge)

So, total no. of nodes $= 25 + 1 = 26$ (No. of nodes in a tree is $1$ more than no. of edges).

Now, no. of leaf  nodes (nodes with $0$ degree) $= 26 - 5 - 10 = 11$.

Correct Answer: $B$

edited by
60 votes
60 votes
In a binary Tree,

no of nodes of degree 2 = no of leaves - 1.

No of nodes of degree 1 do not affect no of leaves !

No of leafs = No of nodes of degree 2 + 1 = 10 + 1 = 11
6 votes
6 votes
In a directed graph indegree of a graph = outdegree

Outdegree = 1*5 + 2*10

Let number of leaves be x

Indegree = x*1 + 14 *1 (all nodes except root have indegree = 1)

Outdegree = indegree

x = 11
4 votes
4 votes
$L$ = $T+ 1$

$L$ = number of leaf node

$T$ =  number of nodes with 2 child

$L =10+1$

$L= 11$
Answer:

Related questions