Internal Nodes vs External Nodes in a Binary Tree

Back to: Data Structures and Algorithms Tutorials

Internal Nodes VS External Nodes in a Binary Tree:

In this article, we will explore the relationship between internal nodes and external nodes, also known as leaf nodes vs. non-leaf nodes in a Binary Tree. Please read our previous article discussing the formulas for calculating the height and the number of nodes in a Binary Tree. First, let’s define what internal and external nodes are.

What are Internal & External Nodes in a Binary Tree?

Internal Node: An internal node, also known as a non-leaf node, is a node that has at least one child node. In other words, it is a node that is not a leaf node, meaning it has descendants. These nodes are also referred to as non-terminal nodes.

External Node (Leaf Node): An external node, also known as a leaf node, is a node that has no children. It is located at the tree structure’s periphery and has no descendants. These nodes are also known as terminal nodes.

Let’s look at some examples to understand the relationship between leaf and non-leaf nodes.

Example 1:

In this example, how many nodes are there with degrees 2, 1, and 0?

As you can see, there are two nodes with degree 2. These two blue nodes each have two direct child nodes.

How many nodes are there with degree 1? There are two nodes with degree 1. These two nodes each have only one direct child node.

How many nodes are there with degree 0? There are three nodes with degree 0, as these three nodes have no direct child nodes. So, the total number of nodes with degrees 2, 1, and 0 are as follows:

Degree (2) = 2

Degree (1) = 2

Degree (0) = 3

Now, let’s look at another example, and then we will derive the formula or relationship between external and internal nodes.

Example 2:

This tree has three nodes with degree 2, 5 with degree 1, and 4 with degree 0. So, the total number of nodes with degrees 2, 1, and 0 are:

Degree (2) = 3

Degree (1) = 5

Degree (0) = 4

Let’s look at our last example, and then we will analyze the internal and external nodes.

Example 3:

In this tree, there is only one node with degree 2, 4 with degree 1, and 2 with degree 0. So, the total number of nodes with degrees 2, 1, and 0 are:

Degree (2) = 1

Degree (1) = 4

Degree (0) = 2

How are Internal and External Nodes Related to Each Other?

In all three examples, nodes with a degree of 1 or 2 are known as internal nodes, and nodes with a degree of 0 are known as external nodes.

We have listed the degrees for all three examples to make it easier to see the values. If you notice carefully, the number of nodes with degree 0 is always one more than the number of nodes with degree 2 in all the examples. Therefore, there is a relationship between the nodes with degree 2 and those with degree 0 but not with those with degree 1.

Degree (0) = Degree (2) + 1

This relationship between degree 0 and degree 2 will always hold true in a binary tree. That concludes the discussion on the binary tree’s relationship between internal and external nodes.

In the next article, I will discuss General Binary Tree vs. Strict Binary Tree with Examples. In this article, I explain Internal Nodes vs External Nodes in a Binary Tree in C Language with Examples. I hope you enjoy this article on Internal Nodes vs External Nodes in a Binary Tree.