Binary Tree

In a normal tree, every node can have any number of children. A binary tree is a special type of tree data structure in which every node can have a maximum of 2 children. One is known as a left child and the other is known as right child.

 

Types of Binary Trees

 Binary trees can be of the following types-

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.

 

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.

 

 

  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.

 

 

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.

 

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).

 

Extended Binary Tree

 

A binary tree can be converted into Full Binary tree by adding dummy nodes to existing nodes wherever required.