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 understand the difference between tree and binary tree. We will also see basic binary tree terminologies and types of binary tree.
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
Lets understand them one by one.
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.
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.
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.
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.
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.
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 🙂
- Binary Tree Introduction - August 1, 2018
- Tree Data Structure Terminologies – Set 2 - July 2, 2018
- Tree Data Structure Terminologies – Set 1 - July 1, 2018
- Immutable class with mutable member fields in Java - April 30, 2018
- Breaking Singleton using reflection and Enum Singleton - January 14, 2018
Comments and QueriesIf 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.