A Binary Tree is a type of tree data structure in which each node has at most 2 children nodes. The node on the left side of a parent node is called the left child and the node on the right side of the parent node is called the right child. In practice, we use the binary search tree which is a type of binary tree.
Node Of A Binary Tree
The node of a binary tree consists of three components.
- Data: It consists of the data part of the node.
- Left: It contains a reference to the left child of the node
- Right: It consists of reference to the right child of the node.
Types Of Binary Tree
There are five types of binary tree.
- Full Binary Tree
- Perfect Binary Tree
- Complete Binary Tree
- Balanced Binary Tree
- Degenerate Tree
Full Binary Tree
It is a binary tree in which each node has 0 or 2 children. In other words, each node except the leave has 2 children.
Perfect Binary Tree
A perfect binary tree is a binary tree in which every internal node has 2 children and every external or leaf node is at the same level.
Complete Binary Tree
A complete binary tree has all the levels filled except the last level where all nodes are as left as possible. Heap data structure uses a complete binary tree for its implementation.
Balanced Binary Tree
A balanced binary tree is a binary tree in which the difference between heights of left and right sub-trees is never more than one.
A tree which has a structure of a linked list. In this tree each internal node has a single child.