In this post, we will look at the binary tree data structure. We will see the different trees and their characteristics.
A binary tree data structure is a hierarchical data structure where each element have maximum 2 children. We call these children as left and right child. In the following example, the left side tree is a binary tree while the right one is not.
In the right tree structure, we have over 2 child nodes for the parent node 2. Let’s look at some points for the binary tree.
If a tree has only 1 node, it’s also a binary tree.
Nodes in the example images are only labeled and they do not represent the number/data for the tree
Before we get in details of the binary tree data structure, let’s refresh some common terminology.
Before we get in to other details, let’s discuss the different types of the tree. I will cover the most popular tree structures.
A full binary tree is a tree with every node has either 0 or 2 children. No node will have only one child.
A tree where every level fully filled (have 2 children) except maybe the last level. For the complete binary tree, we fill the last level from left to right.
A perfect binary tree is both complete and full.All the leaves have the same depth or same level.
A perfect tree is very rare.
Tree traversal is the process to visit all nodes. On a high level, we can group the tree traversal in the following 2 groups.
For the breadth-first traversal, we visit the nodes of the tree by levels from top to bottom and left to right. For the depth-first traversal; we have the following main traversal options (Also look at the following tree for the sample output)
For the In-Order traversal, we visit the left branch then current node and finally the right branch of our tree. If we perform the In-Order traversal on a binary search tree, we get the data in ascending orders. Here is the screen shot outlining the in-order traversal.
Number shows the traversal sequence in the tree
Output: 9, 5, 1, 7, 2, 12, 8, 4, 3, 11
In the pre-order tree traversal, we visit the current node then left tree and finally the right tree. Here is the screen shot outlining the in-order traversal.
Output: 8, 5, 9, 7, 1, 12, 2, 4, 11, 3
With post-order traversal, we visit the left tree then right tree and finally the parent. Let’s see how the traversal sequence looks like:
Output: 9, 1, 2, 12, 7, 5, 3, 11, 4, 8
A binary search tree is a specialized tree which fulfills the following properties:
Some definition allows duplicates in the binary search tree while some don’t allow duplicate keys in BST. Both definitions are correct.
Two binary search trees can store the same values in different ways:
Balanced tree is a tree where
Average | Worst | |
Space | $O(n)$ | $O(n)$ |
Insert | $O(lg(n))$ | $O(n)$ |
Search | $O(lg(n))$ | $O(n)$ |
Delete | $O(lg(n))$ | $O(n)$ |
Let’s cover some strengths and weaknesses of a BST:
In this post, we covered the binary tree and binary search tree data structure. We talked about various types of a tree and what are the different tree traversal techniques. At the end of the post we checked the binary search tree and its time complexities.
Hello!! Welcome to the Java Development Journal. We love to share our knowledge with our readers and love to build a thriving community.
Leave a Reply