3
$\begingroup$

Across two different texts, I have seen two different definitions of a leaf

1) a leaf is a node in a tree with degree 1

2) a leaf is a node in a tree with no children

The problem that I see with def #2 is that if the graph is not rooted, it might not be clear whether a node, n, has adjacent nodes that are its children or its parents

So is it just always safer to go with def #1? Or is def #2 restricted to rooted trees? Why do some authors present these definition differently?

$\endgroup$
1
  • $\begingroup$ #2 is restricted to rooted trees, yes. The idea of children of vertices requires a root. $\endgroup$
    – stackexchanger
    Jul 16, 2019 at 21:41

1 Answer 1

Reset to default
2
$\begingroup$

Let's look at an unrooted tree with two nodes $v_{1}, v_{2}$. Either could be the root, but both are leaves.

Now consider $P_{2}$, a path of length $2$, which has $3$ vertices. Only the middle vertex is not a leaf. If one of the endpoints was selected as the root, it would have exactly child. If the middle vertex was selected, it would be a root that was not a leaf.

While there is a bit of ambiguity with definition (2), I would go with definition (1). It has the most power and least ambiguity. I really don't like definition (2) either.

I hope this clarifies some.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .