Introduction

This article contains some mathematical properties of binary tree. Which will help to grasp some concepts related to data structures. It doesn’t contain properties’ proof in detail.

First Mathematical Property

“The first property is that a binary tree of N internal nodes has N+1 external nodes.”

mathematical property of binary tree
Figure 1: Tree with internal and external nodes

You can see:

  • Internal Nodes (N) = 9
  • External Nodes (N+1) = 9 + 1 = 10

Internal Nodes: The nodes having one or both childern. External Nodes: The nodes having no child.

Second Mathematical Property

“A binary tree with N internal nodes has 2N links, N-1 links to internal nodes and N+1 links to external nodes.”

Figure 2: Tree with internal and external nodes
  • In every rooted tree, each node, except the root, has a unique parent.
  • Every link connects a node to its parents, so there are N-1 links connecting internal nodes.
  • Similarly each of the N+1 external nodes has one link to its parents.
  • Thus N-1+N+1=2N links.

In other way, you can also observe in Figure 2:

  • Internal Nodes (N) = 9
  • Total number of links (2N) = 18
  • Internal links (N-1) = 9-1 = 8
  • External links (N+1) = 9+1 = 10

REFERENCE: CS301 Handouts (page 306 to 308)

Categorized in:

Data Structures, Learning,

Last Update: May 16, 2024