Tree Data Structure-

 

Before you go through this article, make sure that you have gone through the previous article on Tree Data Structure.

 

We have discussed-

• Tree is a non-linear data structure.
• In a tree data structure, a node can have any number of child nodes.

 

In this article, we will discuss about Binary Trees.

 

Binary Tree-

 

Binary tree is a special tree data structure in which each node can have at most 2 children. Thus, in a binary tree, Each node has either 0 child or 1 child or 2 children.

 

Example-

 

 

Unlabeled Binary Tree-

 

A binary tree is unlabeled if its nodes are not assigned any label.

 

 

 

Example-

 

Consider we want to draw all the binary trees possible with 3 unlabeled nodes.

Using the above formula, we have-

 

Number of binary trees possible with 3 unlabeled nodes

= ^{2 x 3}C₃ / (3 + 1)

= ⁶C₃ / 4

= 5

 

Thus,

• With 3 unlabeled nodes, 5 unlabeled binary trees are possible.
• These unlabeled binary trees are as follows-

 

 

Labeled Binary Tree-

 

A binary tree is labeled if all its nodes are assigned a label.

 

 

 

Example-

 

Consider we want to draw all the binary trees possible with 3 labeled nodes.

Using the above formula, we have-

 

Number of binary trees possible with 3 labeled nodes

= { ^{2 x 3}C₃ / (3 + 1) } x 3!

= { ⁶C₃ / 4 } x 6

= 5 x 6

= 30

 

Thus,

• With 3 labeled nodes, 30 labeled binary trees are possible.
• Each unlabeled structure gives rise to 3! = 6 different labeled structures.

 

 

Similarly,

• Every other unlabeled structure gives rise to 6 different labeled structures.
• Thus, in total 30 different labeled binary trees are possible.

 

Types of Binary Trees-

 

Binary trees can be of the following types-

 

 

1. Rooted Binary Tree
2. Full / Strictly Binary Tree
3. Complete / Perfect Binary Tree
4. Almost Complete Binary Tree
5. Skewed Binary Tree

 

1. Rooted Binary Tree-

 

A rooted binary tree is a binary tree that satisfies the following 2 properties-

• It has a root node.
• Each node has at most 2 children.

 

Example-

 

 

2. Full / Strictly Binary Tree-

 

• A binary tree in which every node has either 0 or 2 children is called as a Full binary tree.
• Full binary tree is also called as Strictly binary tree.

 

Example-

 

 

Here,

• First binary tree is not a full binary tree.
• This is because node C has only 1 child.

 

3. Complete / Perfect Binary Tree-

 

A complete binary tree is a binary tree that satisfies the following 2 properties-

• Every internal node has exactly 2 children.
• All the leaf nodes are at the same level.

 

Complete binary tree is also called as Perfect binary tree.

 

Example-

 

 

Here,

• First binary tree is not a complete binary tree.
• This is because all the leaf nodes are not at the same level.

 

4. Almost Complete Binary Tree-

 

An almost complete binary tree is a binary tree that satisfies the following 2 properties-

• All the levels are completely filled except possibly the last level.
• The last level must be strictly filled from left to right.

 

Example-

 

 

Here,

• First binary tree is not an almost complete binary tree.
• This is because the last level is not filled from left to right.

 

5. Skewed Binary Tree-

 

A skewed binary tree is a binary tree that satisfies the following 2 properties-

• All the nodes except one node has one and only one child.
• The remaining node has no child.

OR

A skewed binary tree is a binary tree of n nodes such that its depth is (n-1).

 

Example-

 

 

To gain better understanding about Binary Tree and its types-

Watch this Video Lecture

 

Also Read- Binary Tree Traversal

 

Download Handwritten Notes Here-

 

 

Next Article- Binary Tree Properties

 

Get more notes and other study material of Data Structures.

Watch video lectures by visiting our YouTube channel LearnVidFun.