Mathematical Properties of Binary Tree

Table of Contents

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: