We all know that Binary Tree is one of the most important tree data structure for the technical interview. In this blog post, I have given a brief introduction about the binary tree and its types.
Binary Tree is a Tree data structure in which each node can have maximum of two children. Typically, these children are described as “left child” and “right child” of the parent node.
The above image shows the difference between the General Tree and Binary Tree.
A General Tree is a Tree data structure in which each node can have zero or many child nodes. In general tree, there is no limitation on the degree of a node. The topmost node of a general tree is called the root node. There are many subtrees in a general tree that is unordered because the nodes of the general tree can not be ordered according to specific criteria.
A Binary Tree is a Tree data structure in which each parent node can have maximum of two children or two child nodes. Unlike general tree, binary tree can be empty. Since, binary tree can only have maximum of two child nodes, there is limitation on the degree of a node. This type of tree have mainly two subtrees namely left-subtree and right-subtree and is ordered because the nodes can be ordered according to specific criteria.
There are different types of binary trees
- Full or Strict Binary Tree:
A Full or Strict Binary Tree is a data structure in which each internal node has 0 or 2 child nodes. In other words, in this type of data structure, all the nodes are of degree 0 or 2 ,never degree 1.
2. Perfect Binary Tree:
A Perfect Binary Tree is a Tree data structure in which all the nodes have 2 child nodes. In this type of binary tree, all the leaf nodes are in exact same level or depth.
3.Complete Binary Tree:
A type of tree data structure in which all levels are completely filled and last level has keys as left as possible.
4.Degenerate or Pathological Tree:
In this type of tree data structure, every node has one child node which can be either at left or right.
5.Skewed Binary Tree:
Skewed Binary Tree is a degenerate or pathological type of data structure in which tree is solely dominated by left or right child nodes. All skewed binary trees are degenerate but not all degenerate trees are skewed.
6. Balanced Binary Tree:
It is a type of tree data structure in which the difference between the height of left and right subtree is maximum one for all the nodes.