The Gateway to Computer Science Excellence
0 votes

Leaf Nodes =[ Internal nodes with degree 2 ] + 1

It is valid if we consider Tree as undirected graph ?

Or is it valid only for Tree when considered as directed graph

in DS by
edited by | 113 views
what is the meaning of a directed tree and undirected tree?


see my comment what I ask to you, please defined both terms?

Actually I mean to say Tree as directed graph and Tree as undirected graph
tree and graph both are same?
in question it is not clear?

See this


@Lakshman Patel RJIT

He meant that is that formula true when take tree as directed graph or undirected graph.

@jatin khachane 1

Tree by default is a directed graph so minimum degree is 0 i.e.  deg of leaf. But if we treat in as undirected graph then min deg becomes 1.

But the above formula holds for tree as directed graph.

leaf nodes = internal nodes+1 (for full binary tree)

leaf node=internal nodes with deg2 + 1 (for all trees)



@jatin khachane 1

i suggest you to " Don't remember the formulas, derive them whenever those are required "

it may help you


Thnaks bro @MiNiPanda

Answer m expecting

One more doubt

In undirected : 
A graph is TREE IFF It is connected and has n-1 edges

But this may not be true in directed case right



@Shaik Masthan

I didn't remember it ..i found it one answer i found it may not work for directed case so I put question

you didn't provide any explanation of your approach then how can i think you are not remembering it ?

Anyway it's upto you :)

No need of any further discussions.

@jatin khachane 1

But this may not be true in directed case right

Why so..?


In directed Case : degrees possible 0,1,2

I = nodes with degree 2

L = nodes with degree 0

X = nodes with degree 1

Sum of degrees = Number of edges [since directed]

I(2) + L(0) + X(1) = [I+L+X] - 1

2I + X = I + L + X -1

I = L - 1 ==> L = I +1

@Shaik Masthan

Please correct if wrong :(


@jatin khachane 1

Yes you are right..

And please check the edit i did in my comment..i misread your question at that time..

Please log in or register to answer this question.

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,315 questions
60,426 answers
95,226 users