What is an "internal node" in a binary search tree?

Question

I'm scouring the internet for a definition of the term "Internal Node." I cannot find a succinct definition. Every source I'm looking at uses the term without defining it, and the usage doesn't yield a proper definition of what an internal node actually is.

Here are the two places I've been mainly looking: Link assumes that internal nodes are nodes that have two subtrees that aren't null, but doesn't say what nodes in the original tree are internal vs. external.

http://www.math.bas.bg/~nkirov/2008/NETB201/slides/ch06/ch06-2.html seems to insinuate that internal nodes only exist in proper binary trees and doesn't yield much useful information about them.

What actually is an internal node!?

"Internal" is a synonym for "not a leaf". If the root is not a leaf, it is an internal node. If the root is a leaf, it is not an internal node. — JeffE, May 10 '20 at 20:39

score 97 · Accepted Answer · edited Aug 10 '15 at 03:41

97

     I         ROOT (root is also an INTERNAL NODE, unless it is leaf)
   /   \
  I     I      INTERNAL NODES
 /     / \
o     o   o    EXTERNAL NODES (or leaves)

As the wonderful picture shows, internal nodes are nodes located between the root of the tree and the leaves. Note that the root is also an internal node except in the case it's the only node of the tree.

What is said in one of the sites about an internal node having to have two children is for the tree to be a complete binary tree, not for the node to be internal.

edited Aug 10 '15 at 03:41

Schemetrical

5,506
2
26
43

answered Nov 05 '08 at 16:50

Vinko Vrsalovic

330,807
53
334
373

In the diagram, can you make one of your internal nodes only have one child? This will help to clarify the definition. – Bobby Jack Nov 05 '08 at 16:56
This was my initial intuition, but I have a professor and a book that disagree. – evizaer Nov 05 '08 at 17:38
What's the disagreement about? – Vinko Vrsalovic Nov 05 '08 at 17:44
The 2nd resource you link to in your question states "A binary tree is proper if each internal node has two children." The term "proper" here doesn't mean 'real' or 'valid'; it's just terminology for that type of tree. A generic definition of "internal node" therefore has nothing to do with ... – Bobby Jack Nov 06 '08 at 16:23
5

This is wrong... A root is always an internal node, except when the tree consists of _only_ the root. – Øyvind Nov 16 '11 at 14:46
So, in this figure, there are 3 leaves and 3 internal nodes; so what happens for this formula: `#of leaves = #of internal nodes + 1` – Hengameh Aug 10 '15 at 03:29
1

@Hengameh, that formula applies only to *full* binary trees. A full tree is one in which every node is either a leaf or has exactly 2 children. The left internal node does not have 2 children and so this tree is not full. If that node had a right child node (which would be a leaf node), then the tree would have 4 leaves and the formula would be correct: 3 internal nodes + 1 = 4 leaves. – adino Dec 23 '15 at 01:38
So, in other words, internal nodes are all nodes except the leaf nodes – Hzzkygcs Oct 14 '21 at 02:39

score 17 · Answer 2 · answered Nov 05 '08 at 16:48

17

As far as i understand it, it is a node which is not a leaf.

answered Nov 05 '08 at 16:48

Alphager

1,337
1
10
14

1

That is my understanding of an internal node also. Perhaps it might also not include the root. – Chris Ballance Nov 05 '08 at 16:49
Internal nodes do exclude the root. – Bill the Lizard Nov 05 '08 at 16:56

score 12 · Answer 3 · edited Jan 05 '15 at 11:33

12

From "Introduction To Algorithms", edited by Thomas H Cormen:

A node with no child is called 'leaf node'. A non-leaf node is an 'internal node'.

edited Jan 05 '15 at 11:33

fedorqui

275,237
103
548
598

answered Jan 05 '15 at 11:30

PRADOSH NAYAK

121
1
2

1

Which page is it mentioned on? – Rajat Saxena Jan 12 '17 at 17:24

score 8 · Answer 4 · answered Nov 05 '08 at 16:51

8

An internal node or inner node is any node of a tree that has child nodes and is thus not a leaf node. An intermediate node between the root and the leaf nodes is called an internal node.

Source: http://en.wikipedia.org/wiki/Tree_data_structure

answered Nov 05 '08 at 16:51

tvanfosson

524,688
99
697
795

+1, Also root is an internal node, as well. The only time, root is not internal is, when tree consists of only one node which is root (it will be external, since it is leaf). – Hengameh Jun 18 '15 at 01:17

score 7 · Answer 5 · answered Nov 12 '14 at 18:08

The most upvoted answer is incorrect. According to Mathematical Structures for Computer Science by Judith Gersting, an internal node is "A node with no children is called a leaf of the tree; all non-leaves are called internal nodes"

So, for example (I = INTERNAL NODE): I / \ * I /\ * *

score 4 · Answer 6 · answered Nov 28 '13 at 17:54

4

An internal node (also known as an inner node, inode for short, or branch node) is any node of a tree that has child nodes. Similarly, an external node (also known as an outer node, leaf node, or terminal node) is any node that does not have child nodes.

quick and simple.

answered Nov 28 '13 at 17:54

user1767754

23,311
18
141
164

1

Listing synonyms is useful, so +1. – striving_coder Nov 23 '14 at 01:56

score 3 · Answer 7 · answered Nov 28 '13 at 18:01

3

Internal node: a node which is not the root and has at least one child.

answered Nov 28 '13 at 18:01

freedev

25,946
8
108
125

orcmid · Answer 8 · 2008-11-05T23:47:29.903

Generally, an internal node is any node that is not a leaf (a node with no children).

In extended binary trees (also comparison trees), internal nodes all have two children because each internal node corresponds to a comparison that must be made [The Art of Computer Programming (TAoCP) vol.3 Sorting and Searching, discussion and figure in section 5.3.1, p.181 (ed.2). By the way, the use of these trees to represent pairings (and byes) for elimination tournaments is addressed in section 5.4.1 of this material.]

Vinko's diagram reflects this distinction, although the root node is also always either an internal node or a leaf node, in addition to being the only node with no parent.

There is a broader discussion in Knuth's treatment of information structures and properties of trees [TAoCP vol.1 Fundamental Algorithms, discussion of path lengths in trees in section 2.3.4.5, p.p. 399-406 (ed.3) including exercises (many worked-out in the back of the book)].

It is useful to notice that binary search trees (where internal nodes also hold single values as well as having up to two children) are somewhat different [TAoCP vol.3, section 6.2.2]. The nomenclature still works, though.

score 1 · Answer 9 · answered May 19 '15 at 13:33

1

Internal node – a node with at least one child. External node – a node with no children.

answered May 19 '15 at 13:33

nil96

313
1
3
12

score 0 · Answer 10 · answered Mar 10 '10 at 16:43

Ya internal node does not include the root. And a complete binary tree as terminology tells each internal node should have exact 2 nodes. But in a simple binary tree each internal node have atmost 2 nodes i.e it cannot contain more then 2 nodes but less then 2 is permisable

score 0 · Answer 11 · answered Dec 04 '08 at 04:29

0

A node which has at least one child.

answered Dec 04 '08 at 04:29

Rich

12,068
9
62
94

score 0 · Answer 12 · answered Nov 25 '10 at 08:15

0

A binary tree can have zero , one nodes and can have maximum of two nodes. A binary tree have a left node and a right node in itself.

answered Nov 25 '10 at 08:15

Manoj Singh

9
1

score 0 · Answer 13 · answered Jul 01 '17 at 18:54

0

An internal node or inner node is any node of a tree that has child nodes and is thus not a leaf node or An intermediate node between the root and the leaf nodes is called an internal node

answered Jul 01 '17 at 18:54

SHASHI BHUSAN

612
6
12

What is an "internal node" in a binary search tree?

13 Answers13

Linked