Binary trees are one of the most complicated yet significant forms of data structures. They are used to store data in a hierarchical manner. Have you ever come across the term binary tree in your professional career while storing and managing your data? If yes, you must be curious about several views of binary trees and how you can print them.
Binary trees are data structures in which the data is stored in the form of nodes attached through branches. In binary trees, each node has two daughter nodes that can be considered as the branches of the root.
The flow and accessibility of data are segregated in an organized manner with binary trees.
In this article, we will discuss one of the primary questions asked about binary trees i.e., the bottom view of binary tree and how it is calculated through different approaches.
Before we discuss this particular view of a binary tree, let’s first take a look at all the available views of a binary tree and get a summary of them.
Table of Contents
What are the views of a binary tree?
Just like a physical tree, the binary tree has four main views. These views are:
- Top view of binary tree
- Right view of binary tree
- Left view of binary tree
- And the bottom view of the binary tree
Each view of a binary tree shows different elements placed along their sight. These views are important to understand the accessibility and availability of data in a data structure.
There are different parameters that you can observe through the views of a binary tree. These parameters include the horizontal distance of a node, placement of a node, nodal address, level number of the node, and much more.
These parameters can help you observe the exact value and location of a node.
Let’s discuss one of the most commonly asked views of a binary tree, i.e., the bottom view of a binary tree in detail.
What is the Bottom view of a binary tree?
The bottom view of a binary tree shows the nodes that are seen when a particular binary tree is viewed from the bottom.
By performing pre-transversal order on the elements, you can easily get access to all the nodes and elements that can be found on the bottom view of a binary tree.
Initially, the values of level and node distance from the root are passed for each element to place them adequately in the tree. Afterward, by the pre-transversal order, the nodes available on the end view are showcased with this view.
But there are different ways in which you can print the bottom view of a binary tree through a code.
Let’s discuss the most efficient and accurate methods of implementing the bottom view of a certain binary tree.
Approaches to see the Bottom view of a binary tree
There are two methods through which you can get the bottom view of a tree. These methods use a hashmap and recursion approach and the Queue approach.
We will discuss the hashmap and recursion approach in detail first.
Hashmap and recursion
In this approach, the technique is to add nodes to the map on different conditions based on the horizontal distance. Also, the function is called recursively unless all the nodes at the bottom are accessed.
Following are the steps that show the Hashmap and recursion approach to accessing the bottom view of a binary tree:
- The first step is to perform preorder transversal. This will help you to calculate the appropriate level of different nodes of the whole binary tree from the root to the final node.
- Now, construct a hashmap where you can store all the heights of the nodes. Store the distances in this map accurately
- For the hashmap, keep the key as level or simply the horizontal distance of a particular node. Whereas the value of this map will be a pair (p, q). In this pair, p is the element value for the node, and q denotes the height or horizontal distance of the particular node.
- Afterward, simply for each node of the binary tree, add the node to a resultant map. This node will be only added if the node is the first one to have the same horizontal distance as the current.
- However, in case the node is already available for the same distance, you can replace the previously placed node with the current node value. This will be done only if the current node has a horizontal distance that is relatively more than the previous node.
Finally, get the nodes available on the map. This will be the bottom view of your binary tree. Let’s discuss the Queue approach and observe how it deals with time complexity accurately.
In this approach as well, the pre-order transversal of the nodes is performed and the results are stored in a queue. In addition to the queue, the horizontal distance is to be stored in the map as a key.
Let’s understand the algorithm of this approach:
- First of all, make a queue and store all the nodes after performing the order transversal on every node
- Next, put the value at the root of the binary tree in the queue. This root will be placed at a distance that will be kept at 0 for the root
- Push the left child of the binary tree to the queue one at a time with a horizontal distance as hd-1.
- Whereas the right child will be pushed with horizontal distance as hd+1
- Simply push the elements with respective horizontal distances from the queue to the map unless the queue is found empty.
At last, print the map values that will show the bottom view of the binary tree with appropriate nodes.
Reverse of an array and order transversal are the two major topics that you need to learn to print the bottom view of a binary tree. You can use the approach of your choice according to the amount of data in each array to get the bottom view or any of the four views of the binary tree.