Data Structure - Binary Tree Concepts

Table of Contents

A binary tree is a special kind of tree and important in computer science. There is plenty of real-world application of binary trees. The scope of this lesson is limited to the learning the binary tree concepts.

Learn Tree Basics

Informal definition

A tree is called a binary tree if it has the following properties.

It is an empty tree with no nodes.
The tree has a root node, left sub-tree and right sub-tree.
The sub-trees are binary tree themselves.

Strictly Binary Tree

Suppose there is a binary tree with right sub-tree and left sub-tree. The sub-trees are in turn non-empty, then such a binary tree is called a strictly binary tree.

In the above figure, one is a strictly binary tree and the second tree is not a strictly binary tree, but it is certainly a binary tree and satisfy all the properties of a binary tree.

Complete Binary Tree

A complete binary tree has a level L and all its leaf nodes are available at level L. At each level the complete binary tree contains 2^Lnodes.

Let us show this with an example,

Complete Binary Tree - Binary Tree Concepts — Complete Binary Tree – Binary Tree Concepts

The root is at level 0, therefore, L = 0 and 2^L = 2^0 = 1.

Conversion of a Binary Forest into a Binary Tree

Suppose we have a forest with two trees as follows,

Forest with Two Trees - binary tree concepts — Forest with Two Trees

\begin{aligned} &T1 = { 1,2,3,4,5,6}\\ &T2 = { 7,8,9,10,11,12} \end{aligned}

The figure below show the two separate trees in the forest.

The first step is to order the nodes of both trees using following formula.

If a node has left child, then if comes immediately below the node.
If a node has another node in the save level, then it becomes the right child of the node.
If a node has right child then, ignore it.

Such a representation of two trees is given below.

Forest with Two Ordered Trees - binary tree concepts — Forest with Two Ordered Trees

Your next step should be to join these two tree into one by connecting their roots. This is because the roots of the trees are at the same level. See the figure below

Forest with Two Ordered Trees Joined - Binary tree concepts — Forest with Two Ordered Trees Joined

The new tree is a binary tree, the node at the save level in above diagram becomes the right child. The final tree structure look like the one in figure below.