Types of Trees in Data Structure

1.       General Tree

If a tree has no constraint on its hierarchy then it is called a General tree. All the nodes may have an infinite number of child nodes.

2.       Binary Tree

If a tree has exactly two child nodes for each parent node then it is called a Binary tree. The children are known as the left child and the right child.

3.       Binary Search Tree

It is an extension of Binary tree with several optional restrictions. The value of the left child node should be less than or equal to the parent value and the value of the right child node should always be greater than or equal to the parent’s value.

4.       AVL Tree

AVL tree is an abbreviation of Adelson-Velshi and Landis tree. It is Binary Search Tree self-balancing. This was the first tree that dynamically balanced itself. A balancing factor is allocated for each node in the AVL tree, based on whether the tree is balanced or not. In the AVL tree, the correct balance factor is 1, 0 and -1. If the tree has a new node, it will be rotated to ensure that it is balanced. It will then be rotated.

5.       Red-Black Tree

This is another type of auto-balancing tree. Each node is either colored red or black. It maintains the balance of the tree. When the new nodes are added in Red-Black Tree, nodes will be rotated to maintain the Red-Black Tree’s properties.

6.       N-ary Tree

In this tree, the maximum number of children with a node is N. Each node of the binary tree has two children whereas a node of N-ary tree has either 0 or N children.