1
$\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$
  • $\begingroup$ #2 is restricted to rooted trees, yes. The idea of children of vertices requires a root. $\endgroup$ – stackexchanger Jul 16 at 21:41
1
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.