Bottom View of a Binary Tree in Java

Data structures are the core of any programming language!

Hence,as a programmer, you should be well aware of data structures to master the basics of coding.

One data structure which is generally used to resolve real-world problems is a binary tree. This tree-like structure has different nodes connected where one node behaves as a root node and the other behaves as a child node.

However, the catch here is that one node can not have more than two children. Besides all this, binary trees are widely used in programming languages making it one of the favourite topics of an interviewer.

One such question which is commonly asked in a coding interview is how to view the bottom view of binary tree.

Before understanding this problem, let's understand the meaning of a binary tree.

What Is A Binary Tree?

A binary tree is a tree-like data structure which has a maximum of two children. In a binary tree, there are only two children allowed which are generally named right and left child.

You can represent a binary tree with the help of a pointer pointing to the uppermost node of the binary tree. In case, the given tree is null, the value of its root will also be NULL.

Understanding The Problem Statement

In this problem, you will be provided with a binary tree having integer values. Here, you will have to write a program to print an array of integers which represents the bottom view of the given binary tree.

Here, the bottom view of binary tree is defined as the set of nodes that you can view when you visit the given tree from the bottom.

Methods to View Bottom View Of A Binary Tree

To print the bottom view of a binary tree, you can use the following two methods:

• Recursion or hashmap approach

• Queue approach

Here, we will discuss each of these approaches in detail.

Recursion Or Hashmap Approach

The most basic method that you can use to print the bottom view of a binary tree is the hashmap approach.

In this approach, you have to follow below steps:

• You need to carry out a preorder traversal and calculate each node level of the binary tree.

• Now, consider using a hashmap and you need to store the map's height to this hashmap. Here, the key is defined by the level or horizontal distance of the node. The value of the key will be represented as a pair (p, q) in which p depicts the node's value and q represents the node's height.

• Now, for each node, perform the following operations:

in case the selected node is the initial node having horizontal distance, you will have to add this node to the map.

Otherwise, in case the node is present for the specified distance, you will have to replace the existing node with the present chosen node in case this node's height is greater than the existing one.

Complexity Analysis

• Time Complexity: Now that there is n number of nodes present in the graph, the time complexity in this method will be calculated as O(n).

• Space Complexity: Since we are using an auxiliary map in this approach, the space complexity of this method will be calculated as O(n).

Queue Approach

Another approach that you can use to print the bottom view of a binary tree is using a queue approach. In this method, you will have to perform the traversal of the tree and then store the values in the queue.

Other than this, you can also consider a map to store the distance between the root and nodes as its key.

To use the queue approach, you need to follow the steps mentioned below.

• To begin with, to perform the level order traversal, you will first have to declare and initialise the queue.

• Now, you need to add the binary tree's root to the queue. Also, add the horizontal distance which will be 0.

• You will now have to push all the left children into the queue. Also, add their horizontal distance. Here, the horizontal distance for the left node will be -1 whereas for the right child it will be +1.

• Now, while the queue has elements, carry out the following steps:

Add the front element of your queue as a variable, let's say, front.

Now, pop one element.

Add the Dequeued element to the front and then update the value of the front in the map.

In case there is a left child available, you will have to push it in the queue. Also, add the horizontal distance as -1.

However, if there is a right child present, you will have to push it in the queue. Also, add the horizontal distance as +1.

• In the end, you need to print all the values present in the map containing the binary tree's bottom keys.

Complexity Analysis

• Time Complexity: The time complexity of this method is calculated as O(n* log n). Here, n represents the number of elements.

• Space Complexity: Here, we are using a map to store the data. Therefore, the space complexity is calculated as O(n).

Now that we are discussing common coding problems, the list is incomplete without the equal sum partition problem.

Here, we will be provided with an array consisting of integer values. You will have to write a program to divide the given array into two different subsets in such a way that the sum of integers present in subset 1 is equal to the sum of integers present in subset 2.

To resolve the equal sum partition problem, there are two approaches that you can use. One of these approaches is the brute force approach which is a basic approach that you can use.

Another approach that you can use is the dynamic programming approach.

Conclusion

A binary tree is a tree with not more than two nodes. When it comes to viewing the bottom view of a binary tree, you can either use a hashing approach or use a queue-based approach.

In both these approaches, additional space is used which in turn increases the space complexity of these algorithms.