12

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?

Community
  • 1
  • 1
jantristanmilan
  • 4,188
  • 14
  • 53
  • 69
  • 1
    Yeah I know what you mean, I would probably ask the instructor if that's what you're worried about. Personally I wouldn't call the root an "internal" node but I don't know how much consensus you're going to get on this... – user541686 Jan 18 '13 at 05:02
  • Agreed. Depending on who you ask, you will get a different answer. – Justin Jan 18 '13 at 05:03

5 Answers5

17

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
Maciej Szpakowski
  • 571
  • 1
  • 7
  • 22
Utkarsh
  • 318
  • 2
  • 9
0

Yes root node is an internal node.
[More explanation]

A root node is never called as a leaf node even if it is the only node present in the tree. For ex. if a tree has only one node then we say that it is a tree with only root node, we never say that the tree has a single leaf node.
Since internal node means a non-leaf node and because root node is never considered as leaf node I would say that in case of single node tree root node is an internal node.

user85
  • 1,526
  • 5
  • 26
  • 42
0

IMHO when you are talking about a tree with more than one node we can say the root node is an internal node. When there is only one node (the root node) the question of internal node doesn't arise. Hence we can vacuously say it is an internal node.

Panduranga Rao Sadhu
  • 448
  • 1
  • 7
  • 23
0

"A node with no children is a leaf or external node. A non-leaf node is an internal node."

Source: "Introduction To Algorithms-3rd edition" page number 1176, last line.

So, root is also an internal node except when it is the only node of the tree.

RobC
  • 22,977
  • 20
  • 73
  • 80
Dhruv Joshi
  • 33
  • 1
  • 7
0

Yes. Per CLRS B.5.2:

A node with no children is a leaf or external node. A nonleaf node is an internal node

xxks-kkk
  • 2,336
  • 3
  • 28
  • 48