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

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