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

evizaer picture evizaer · Nov 5, 2008 · Viewed 73.6k times · Source

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

Vinko Vrsalovic picture Vinko Vrsalovic · Nov 5, 2008
     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.