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: http://planetmath.org/encyclopedia/ExternalNode.html 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!?

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

A node which has at least one child.

Answer 5

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