GATE CSE 1995 | Question: 1.17

Question

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

• A. $\log_2 n$
• B. $n-1$
• C. $n$
• D. $2^n$

Comments

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 n₂=n₀-1 ( where n₂ is # Internal nodes having degree 2 & n₀ is # leaves with degree 0)

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

Answer 1

In Binary Tree a node can have at most $2$ children.

Total number of node $\mathbf{N} =$ node with $0$ child $+$ node with $1$ child $+$ node with $2$ child.

$\implies 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)$

$\implies N=n + n_1 + n_2$

Total number of edges $e=N-1,$ and also $e = n \ast 0+ n_1 \ast1 + n_2 \ast 2$

$\therefore N-1 = n \ast 0+ n_1 \ast1 + n_2 \ast 2$

$\implies n + n_1 + n_2 - 1 = n_1 \ast1 + n_2 \ast 2$
 
$\implies \mathbf{n_2 = n -1}$

Option B is answer.

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

Comments

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 :)

---

degree of leaf node is 1 ??

but see this

https://www.google.co.in/search?site=&source=hp&q=degree+of+leaf+node&oq=degree+of+leaf+node&gs_l=psy-ab.3...1231.8939.0.9367.0.0.0.0.0.0.0.0..0.0....0...1.1.64.psy-ab..0.0.0.0vOu1kreuS4

---

:) 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

$N=mi+1$

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.

2i+1=i+l

$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

 

https://gateoverflow.in/2604/gate1995-1-17?show=140932#c140932

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.

 

@MiNiPanda

---

Wow That was a very beautiful explanation

---

IN BINARY TREE .(2-DEGREE).

INTERNAL NODE  N = (N+1) LEAF.

SO ,

N LEAF = (N-1) INTERNAL NODE .

---

I’ve seen this ton of times but never came across it’s proof.

Thanks man

#HappyLearning

---

Awesome explanation! I solved this question in different ways, but this method is very intuitive!

Answer 2

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

So Ans = n-1

Comments

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.

Answer 3

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.

Comments

can you plz give example

Answer 4

https://youtu.be/RX3r5chA6gI