In computer science, a binary tree is a special type of generic tree in which each node has at most two children, which are referred to as the left child and the right child.
We can also say this in the way that no node can have more than two child nodes in the binary tree. Each binary tree is a tree but each tree is not a binary tree. A complete binary tree has the degree of the entire internal node and all the levels are on the same level.
Binary tree has the following properties.
- Binary tree which has n internal node internal node can have maximum n + 1 external node, here root node is also counted as internal node
- The length of an external path is twice the length of the internal path in a binary tree that has n internal nodes.
- The binary tree that has n internal node has a height of about log2n.
Types of Binary Tree
Full Binary Tree
All nodes in the Full Binary Tree have either 0 or 2 child nodes. if a binary tree has all the nodes of either left and right child or no child, then the binary tree is called full binary tree. Full Binary tree is also called Strictly binary tree. A Full binary tree with n leaves will have (2n - 1) nodes.
Complete Binary Tree
A binary tree is called a complete binary tree has 2 child nodes of all nodes and all the leaf nodes at the same level. If the left side tree in the Complete Binary Tree has 2 children, then the right side must also have 2 children, that is, the leaf nodes must be at the same level, if there is not the same level then it will not be the Complete Binary Tree.
Skewed Binary Tree
All nodes in a skewed binary tree have left child or right child nodes called a skewed binary tree.The skewed binary tree has only the left side node and only the right side child node
Extended Binary Tree
A binary tree is called an extended binary tree when all its nodes have either 0 or 2 child nodes. In an extended binary tree, internal nodes are represented by circles and external nodes are represented by rectangles.
The nodes that have 2 child nodes are called internal nodes and the nodes which have 0 child nodes are called external nodes.