The Gateway to Computer Science Excellence
+28 votes

A binary tree $T$ has $n$ leaf nodes. The number of nodes of degree $2$ in $T$ is

  1. $\log_2 n$
  2. $n-1$
  3. $n$
  4. $2^n$
in DS by
edited by | 8.7k views

Key Point: Don't memorize these relations between Internal nodes and leaf nodes. It varies as per definition of degree. So go by definition in question ONLY.

Like if "Degree is # of children of a node" than its n2=n0-1 ( where n2 is # Internal nodes having degree 2 & n0 is # leaves with degree 0)

And if "Degree is # of neighbors of a node" than its n3=n1-2 ( where n3 is # Internal nodes having degree 3 & n1 is # leaves with degree 1)

7 Answers

+57 votes
Best answer

In Binary Tree a node can have at most $2$ children.
Total number of node $ \Rightarrow \mathbf{N} =$ node with $0$ child $+$ node with $1$ child $+$ node with $2$ child.

$N= n_0 + n_1 + n_2$ (here, in question it is given that no. of leaf nodes i.e no. of nodes with $0$ children is n so $n_0 = n$ )
$N=n + n_1 + n_2$
Total number of edges 
and also $e = n * 0+ n_1 *1 + n_2 * 2$

$N-1 = n * 0+ n_1 *1 + n_2 * 2$
$n + n_1 + n_2 - 1 = n_1 *1 + n_2 * 2$
$\mathbf{n_2 = n -1}$

Option B is answer.

NOTE - For tree, Degree of a node is defined as the number of sub-trees of the node or no of children of a node ...

edited by
can't believe how many times this same question is asked :)
what is n2 here  ??

I think it is nodes having 2 child right ??

But question asks no. of nodes of degree 2 right ??

And nodes having 2 child can also have 3 degree right ??
definition of degree for graph and tree are different.

for graph, degree means no of edges connected to node (in undirected graph), or no of edges incoming or outgoing from node (in directed graph, as fanin-fanout or as indegree-outdegree)

for tree, degree means no of children (something equal to fanout in graph)
sum of degree  

= 2e rt ..then he is doing only e , i am getting something wrong ??

one more thing degree of node is defined by no of subtree of that node
@sid1221 e = n0 * 0 + n1 * 1 + n2 * 2, is not the sum of degrees. Since the degree of a node with zero child is 1 (not 0). That equation is a way of counting edges. Edges below a node with 2 children = 2, below a node with 1 child = 1, and below a leaf node = 0. Hope it clears your doubt :)
:) Thanks. But both terms are defined in different ways. Degree in graph theory for an undirected graph is the number of edges adjacent to a vertex. And using this definition we can say that summation of all degrees is equal to 2 times the number of edges(since each edge contributes 2 to the overall degree of the graph). You are matching this with e = n0*0 + n1*1 + n2*2, which is different. Hope this time it's clear:)
ok i got this equation  but if i do with 2e= sum of degree then getting different ans
clear now thanks :)

Given it's a binary tree

In a "m-ary" tree. the number of total nodes are given by


Where i: Number of internal nodes

Also, in a tree, N=I+L where L=number of leaf nodes

Here m=2

So, N=2i+1.


$L=I+1$ The number of leaves are 1 plus the number of internal nodes in binary tree.

Here, given L=n, subsitute above and we will get I=n-1.


@Rishabh Gupta 2

But in this expression of 'e' , aren't we counting some edges more than once ?

eg. left skewd tree of 3 nodes. middle node have 2 nodes connected with two edges , so they are counted here.

Now leaf node is connected to middle node with same edge which is now counted twice

Please clear the flaw in my arguement.



Wow That was a very beautiful explanation
+5 votes

No of nodes with degree 2 in a  Binary tree = no. Of leaf nodes-1

So Ans = n-1

can you  give example plz
Take any normal binary tree and just number of node having out degree 2
Great explanation.

@Mudrakola Karthik 3

For graph and Tree definition of degree is different -

In Graph:- Number of edges connected with the node (both indegree and outdegree) is the degree of the node.

In Tree:- Number of children of the node is the degree of that node.

So by induction method we can easily prove that Binary tree with n leaf nodes can have n-1 nodes with degree 2.

+3 votes
Here in question there are few inconsistency.

Assumption 1: here we will strictly talk about complete binary tree ( complete binary tree means a node can have either 0 or 2 child basically node with single child is out of consideration)

Assumption 2: Here by degree 2 it is considered as node with 2 children. ( In general it is not so for internal node of binary tree can have atmost 3 degree 2 of child and 1 of parent)

So if above 2 statements are filled. we can say a general statement that such an tree of n leaf nodes are there then number of internal node will always be n-1.

And say we are considering assumption 2 then all n-1 node will have exactly 2 children thus n-1 is most suitable answer.
can you plz give example
+2 votes
0 votes
The highly rated answer for this question on GO is excellent still I would like to tell intuition behind the concept

Let n be total number of leaf nodes, intuition is for every 2 leaf nodes there must be a node where separation occurs (that is degree of node 2) to generate two leaf nodes otherwise if no such node exists then there are two trees, so now consider all the node where separation occurred, as leaf node all at same time now for them also separation must occur this will go on till we reach to the 1 i.e n/2 internal, then after considering n/2 as internal their n/4 internal and so on till we reach 1, so n/2+n/4+n/8+...+n/2^log n =n*(1-(1/2)^log(n)-1)/1-0.5= n-1 internal node
–1 vote
Ans: B
–2 votes
ans is B.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,375 questions
60,614 answers
95,433 users