Is the root node an internal node?
Statement from a book : Discrete Mathematics and Its Applications - 7th edition By Rosen says,
Vertices that have children are called internal vertices. The root is an internal vertex unless it is the only vertex in the graph, in which case it is a leaf.
Supportive Theorem:
For any positive integer n, if T is a full binary tree with n internal vertices, then T has n + 1 leaves and a total of 2n + 1 vertices.
case 1:
O <- 1 internal node as well as root
/ \
O O <- 2 Leaf Nodes
case 2: Trivial Tree
O <- 0 internal vertices (no internal vertices) , this is leaf
jantristanmilan
Updated on July 11, 2022Comments
-
jantristanmilan almost 2 years
So I've looked around the web and a couple of questions here in stackoverflow here are the definition:
- Generally, an internal node is any node that is not a leaf (a node with no children)
- Non-leaf/Non-terminal/Internal node – has at least one child or descendant node with degree not equal to 0
- As far as i understand it, it is a node which is not a leaf.
I was about to conclude that the root is also an internal node but there seems to be some ambiguity on its definition as seen here:
What is an "internal node" in a binary search tree?
- As the wonderful picture shows, internal nodes are nodes located between the root of the tree and the leaves
If we follow that definition then the root node isn't going to be counted as an internal node. So is a root node an internal node or not?
-
user85 over 9 yearscan you please elaborate why you think this is a wrong answer?
-
Maciej Szpakowski over 9 yearsA root node is called leaf if it is the only node. Answer below is correct.