Types of Binary Tree | Binary Tree Introduction
This is the third article in the tree data structure series. In our previous two articles, we have seen some of the tree data structure terminologies like Nodes, Edges, Root, Parent, Children, Leaves, Siblings, Degree of Tree, Path, Level, Depth, Height and sub tree.
In this article, we will discuss difference between tree and binary tree. We will also discuss about types of binary trees and some of the interview questions related to them.
Tree vs Binary Tree
Binary Tree is a special type of Tree data structure in which no node can have more than two children. Typically these children are described as "left child" and "right child" of the parent node.
There are different types of binary trees like,
- Full or Strict Binary Tree
- Perfect Binary Tree
- Complete Binary Tree
- Degenerate or Pathological Tree
- Skewed Binary Tree
- Balanced Binary Tree
Programmers and Authors around the world have different opinions regarding the definition of Full, Strict, Perfect and Complete Binary Tree. We will discuss them in detail in this article. Lets understand them one by one.
1. Full or Strict Binary Tree
A Binary tree is said to be Full Binary Tree, if all its internal nodes has 0 or 2 children. In other words, if all the nodes other than leaf nodes has 0 or 2 children, then that it is Full Binary Tree.
In other words, all of the nodes in a Full or strictly binary tree are of degree zero or two, never degree one.
Full Binary Tree can be used to represent mathematical expression. Here are some of the example of Full Binary Trees.
2. Perfect Binary Tree
A Binary tree is said to be Perfect Binary Tree, if all its internal nodes has exactly 2 children. In Perfect Binary Tree, all leaf nodes are on the same level or depth. Here are the examples
3. Complete Binary Tree
A Binary tree is said to be complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible. Don't confuse it with Perfect Binary Tree. Lets define Complete Binary Tree with respect to Perfect Binary Tree.
A Perfect Binary Tree whose rightmost leaves (perhaps all) on the last level have been removed is called Complete Binary Tree.
Perfect vs Complete Binary Tree: Some authors also refer Perfect Binary Tree as Complete Binary Tree. And they call Complete Binary Tree as Almost Complete Binary Tree or Nearly Complete Binary Tree. Any way, it doesn't matter what name you give to these trees. You should just know the concepts.
A degenerate or Pathological Tree is a Tree where every parent node has only one child either left or right.
Such trees are performance-wise same as linked list. In fact, compartively it provides slow performance than LinkedList as while traversing, you need to first check whether tree has left child or right child and then move to next node.
5. Skewed Binary Tree
A binary tree, which is dominated solely by left child nodes or right child nodes, is called a skewed binary tree, more specifically left skewed binary tree, or right skewed binary tree.
All Skewed trees are pathological trees, but all pathological trees are not skewed trees.
6. Balanced Binary Tree
Binary tree is called Balanced Binary Tree, if difference of left and right subtree height is maximum one for all the nodes.
If any one node violates this rule i.e. Difference of left and right subtree height is more than one, then that tree is not balanced.
Below diagram shows the example of Balanced and Non-balanced Binary Tree. We have also shown pair of left and right subtree height of each node i.e. (Left Subtree Height, Right Subtree Height)
Tree which balances by itself when we insert new element to it is called Self Balanced Binary Tree. For Example, AVL Tree, Red-Black Tree, etc. We will learn more about self balanced binary trees in upcoming articles.
Summary
After reading this article, you should be able to answer following interview questions related to types of Binary Tree.
- Tree vs Binary Tree
- Full vs Complete vs Perfect Binary Tree
- What is Expression Tree?
- What is degenerate or pathological tree?
- What is left and right skewed tree?
- What is Balanced Binary Tree?
That's all for this topic. If you guys have any suggestions or queries, feel free to drop a comment. We would be happy to add that in our post. You can also contribute your articles by creating contributor account here.
Happy Learning 🙂
If you like the content on CodePumpkin and if you wish to do something for the community and the planet Earth, you can donate to our campaign for planting more trees at CodePumpkin Cauvery Calling Campaign.
We may not get time to plant a tree, but we can definitely donate ₹42 per Tree.
About the Author
Tags: DataStructure, Tree, x vs y
Comments and Queries
If you want someone to read your code, please put the code inside <pre><code> and </code></pre> tags. For example:<pre><code class="java"> String foo = "bar"; </code></pre>For more information on supported HTML tags in disqus comment, click here.
