Bottom View of a Binary Tree

You are given a Binary Tree. We will suppose the left and right children of a node make an angle of 45 degrees with the parent node. You have to print the bottom view of the tree from left to right. Some points to keep in mind before approaching this question

Horizontal distances of:
1. Root node to root node = 0.
2. Right child to the root node = 1
3. Left child to the root node = -1.
If node n is the right child, then its distance from the root will be equal to the distance of its parent node +1.
If node n is the left child, then its distance from the root will be equal to the distance of its parent node -1.

Let’s understand the problem statement with an example:

Example 1:

Output: 4 5 6 7

Explanation:

The horizontal distance of the root node i.e. 1 is clearly 0.
2 is the left child of 1, so its distance will be 0-1= -1
2 is the right child of 1, so its distance will be 0+1= 1
Just like that, the horizontal distances of
1. 4 is -2
2. 5 is 0
3. 6 is 0
4. 7 is 2

Since at horizontal distance 0, there are two nodes, node 6 will be considered at the bottom-most level, as it is more towards the right side. Therefore, if we see the bottom-most nodes, what we get is 4 5 6 7

Approach 1: Using Queue

In this approach, we will be using a queue. We will traverse the Binary Tree in the level order fashion, insert the nodes in the queue. Level order traversal is iterating the tree in the order of breadth i.e, the first root node, then the children of the root node, etc We will be using the map to store the horizontal distance of each node.

Algorithm

Create an ordered map and a queue. The horizontal distances of the nodes will be stored in the map while the queue will store the nodes according to level order traversing.
Use the pair<> to store the root and the horizontal distance in the queue.
Check if the queue is empty or not. If not, then:

Create a variable ‘temp’ to store the front node of the queue and the horizontal distance of that node.
Pop the front element.

Iterate over and store the values of each key in a vector.
The vector thus obtained will contain the bottom view node.
Return the vector.

The implementation of the above-discussed approach is:

CPP

#include<bits/stdc++.h>
using namespace std;

// Structure to create a node
// having an integer value, data
// and two pointers
// to store the references of the
// left and right children
struct Node
{
    int data; 
    
    // variable to store horizontal 
    // distance of a node 
    int hd; 
    Node *left, *right; 

    Node(int key)
    {
        data = key;
        hd = INT_MAX;
        left = right = NULL;
    }
};

// function that takes the node
// of a tree as its parameter
// and print the tree's bottom view.
void BottomMostView(Node *root)
{
    if (root == NULL)
        return;

    // variable to store horizontal 
    // distance of a node.
    // initially set it to 0.
    int hd = 0;

    // a map to store the 
    // pair of key and value
    map<int, int> m;

    // queue for storing the nodes of the tree, while
    // traversing the tree in level order.
    queue q;

    // set the horizontal distance of the root node
    // which is intialized to 0.
    root->hd = hd;

    // add the root to the queue.
    q.push(root); 

    // traverse in a level order fashion
    // until queue becomes empty
    while (!q.empty())
    {
        Node *temp = q.front();
        q.pop();

        // get the horizontal distance
        // of the node that is popped out
        // from the queue.
        hd = temp->hd;

        // the popped out node will be 
        // placed in the map with 
        // a key as its horizontal distance.
        m[hd] = temp->data;

        // add the left child of the popped out node,
        // into the queue,
        // with hd = hd - 1
        if (temp->left != NULL)
        {
            temp->left->hd = hd-1;
            q.push(temp->left);
        }

        // add the right child of the popped out node,
        // into the queue,
        // with hd = hd + 1
        if (temp->right != NULL)
        {
            temp->right->hd = hd+1;
            q.push(temp->right);
        }
    }

    // iterate over the nodes in the map.
    for (auto i = m.begin(); i != m.end(); ++i)
        cout << i->second << " "; } // Driver Code int main() { Node *root = new Node(1); root->left = new Node(2);
    root->right = new Node(3);
    root->right->left = new Node(5);
    root->right->right = new Node(6);
    root->right->left->left = new Node(7);
    root->right->left->right = new Node(8);
    
    BottomMostView(root);
    return 0;
}

Output

7 5 8 6

JAVA

import java.util.*;
import java.util.Map.Entry;

// Class to create a node
// having an integer value, data
// and two pointers
// to store the references of the
// left and right children
class Node
{
    int data; 

    // variable to store horizontal 
    // distance of a node 
    int hd; 
    Node left, right; 

    public Node(int key)
    {
        data = key;
        hd = Integer.MAX_VALUE;
        left = right = null;
    }
}

class Tree
{
    Node root; 

    // Default constructor
    public Tree() {}

    // Parameterized constructor
    public Tree(Node node)
    {
        root = node;
    }

    // method that takes the node
    // of a tree as its parameter
    // and print the tree's bottom view.
    public void BottomMostView()
    {
        if (root == null)
            return;

        // variable to store horizontal 
        // distance of a node.
        // initially set it to 0
        int hd = 0;

        // a map to store the 
        // pair of key and value
        Map<Integer, Integer> map = new TreeMap<>();

        // queue for storing the nodes of the tree, while
        // traversing the tree in level order.
        Queue queue = new LinkedList();

        // set the horizontal distance of the root node
        // which is intialized to 0.
        root.hd = hd;

        // add the root to the queue.
        queue.add(root);

        // traverse in a level order fashion
        // until queue becomes empty
        while (!queue.isEmpty())
        {
            Node temp = queue.remove();
            
            // get the horizontal distance
            // of the node that is popped out
            // from the queue.
            hd = temp.hd;

            // the popped out node will be 
            // placed in the map with 
            // a key as its horizontal distance.
            map.put(hd, temp.data);

            // add the left child of the popped out node,
            // into the queue,
            // with hd = hd - 1
            if (temp.left != null)
            {
                temp.left.hd = hd-1;
                queue.add(temp.left);
            }
            // add the left child of the popped out node,
            // into the queue,
            // with hd = hd + 1
            if (temp.right != null)
            {
                temp.right.hd = hd+1;
                queue.add(temp.right);
            }
        }

        // map's values are extracted to a set
        // so that the iterator can iterate over it
        Set<Entry<Integer, Integer>> set = map.entrySet();

        // Iterator to traverse over the set
        Iterator<Entry<Integer, Integer>> iterator = set.iterator();

        // Traversing elements of the map with the iterator.
        while (iterator.hasNext())
        {
            Map.Entry<Integer, Integer> me = iterator.next();
            System.out.print(me.getValue()+" ");
        }
    }
}

// Main driver class
public class BottomMostView
{
    public static void main(String[] args)
    {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.right.left = new Node(5);
        root.right.right = new Node(6);
        root.right.left.left = new Node(7);
        root.right.left.right = new Node(8);
        Tree tree = new Tree(root);
        
        tree.BottomMostView();
    }
}

Output

7 5 8 6

Python

# Class to create a node
# having an integer value, data
# and two pointers
# to store the references of the
# left and right children
class Node:
    
    def __init__(self, key):
        
        self.data = key
        self.hd = 1000000
        self.left = None
        self.right = None


# method that takes the node
# of a tree as its parameter
# and print the tree's bottom view.
def BottomMostView(root):

    if (root == None):
        return
    
    # variable to store horizontal 
    # distance of a node.
    # initially set it to 0
    hd = 0
    
    # a map to store the 
    # pair of key and value
    m = dict()

    # queue for storing the nodes of the tree, while
    # traversing the tree in level order.
    q = []

    # set the horizontal distance of the root node
    # which is intialized to 0.
    root.hd = hd
    
    # add the root to the queue.
    q.append(root)

    # traverse in a level order fashion
    # until queue becomes empty
    while (len(q) != 0):
        temp = q[0]
        
        q.pop(0)
        
        # get the horizontal distance
        # of the node that is popped out
        # from the queue.
        hd = temp.hd

        # the popped out node will be 
        # placed in the map with 
        # a key as its horizontal distance.
        m[hd] = temp.data

        # add the left child of the popped out node,
        # into the queue,
        # with hd = hd - 1
        if (temp.left != None):
            temp.left.hd = hd - 1
            q.append(temp.left)

        # add the left child of the popped out node,
        # into the queue,
        # with hd = hd + 1
        if (temp.right != None):
            temp.right.hd = hd + 1
            q.append(temp.right)

    # Traversing elements of the map with the iterator.
    for i in sorted(m.keys()):
        print(m[i], end = ' ')
        
# Driver Code
if __name__=='__main__':
    
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.right.left = Node(5)
    root.right.right = Node(6)
    root.right.left.left = Node(7)
    root.right.left.right = Node(8)
    
    BottomMostView(root)

Output

7 5 8 6

Complexity Analysis

Time Complexity : O(n*log(n)), where ‘n’ is the number of nodes in the binary tree. Since we are traversing all the nodes of the binary tree in level order traversing and we know that the complexity to insert in an ordered map is log n. Space Complexity: O(n), where ‘n’ is the number of nodes in the binary tree as the queue used in the approach is of the size n.

Approach 2: Using Recursion and Map

This is an optimized approach, with reduced time complexity. We will use both recursion and map in this approach. The map will be used to store a key which is the horizontal distances of the nodes and a pair<a, b> where a is the value of the node and b is the height of the node.

Algorithm

Create a map that will be used to store a key, which is the horizontal distances, “hd” of the nodes and a pair<a, b> where a is the value of the node and b is the height of the node.
The root node will be the starting point, so its horizontal distance and height, both will be 0, and the horizontal distances and heights of all other nodes will be computed with reference to the root node.
If for some horizontal distance there is no node present, then insert it into the map
Recursively find the bottom-most node in the left subtree.
Use recursion on the left subtree to find the height and horizontal distance. As it is the left child of the node, height will be height + 1, and its horizontal distance from the existing node will be the horizontal distance of the current node-1
Again Use recursion on the left subtree to find the height and horizontal distance. As it is the left child of the node, height will be height + 1, and its horizontal distance from the existing node will be the horizontal distance of the current node+1
The vector thus obtained will contain all the bottom view nodes.
Return the vector.

. The implementation of the above-discussed approach is:

CPP

#include <bits/stdc++.h>
#include <map>
using namespace std;

// Structure to create a node
// having an integer value, data
// and two pointers
// to store the references of the
// left and right children
struct Node
{
    // data of the node
    int data;

    // variable to store horizontal 
    // distance of a node 
    int hd;
    
    Node * left, * right;
    
    Node(int key)
    {
        data = key;
        hd = INT_MAX;
        left = right = NULL;
    }
};

// Helper function to recursively
// find a tree's bottom view.
void findBottomViewUtil(Node * root, int curr, int hd, map <int, pair <int, int>> & m)
{
    // Base case
    if (root == NULL)
        return;
    
    // if for some hd
    // there is no node present,
    // then insert it into the map
    if (m.find(hd) == m.end())
    {
        m[hd] = make_pair(root -> data, curr);
    }

    // case to handle the situation
    // having more than one nodes at a 
    // certain hd 
    else
    {
        pair < int, int > p = m[hd];
        if (p.second <= curr) { m[hd].second = curr; m[hd].first = root -> data;
        }
    }
    
    // recursively find bottom-most node
    // in the left subtree 
    findBottomViewUtil(root -> left, curr + 1, hd - 1, m);
    
    // recursively find bottom-most node
    // in the right subtree 
    findBottomViewUtil(root -> right, curr + 1, hd + 1, m);
}

// function that takes the node
// of a tree as its parameter
// and print the tree's bottom view.
void BottomMostView(Node * root)
{
    
    // create a map
    // for storing the
    // hd, height and data of the nodes
    map < int, pair < int, int > > m;
    
    findBottomViewUtil(root, 0, 0, m);

    // the map containing the bottom-most nodes
    // returned by the function
    // findBottomView()
    map < int, pair < int, int > > ::iterator it;
    for (it = m.begin(); it != m.end(); ++it)
    {
        pair < int, int > p = it -> second;
        cout << p.first << " "; } } int main() { Node *root = new Node(1); root->left = new Node(2);
    root->right = new Node(3);
    root->right->left = new Node(5);
    root->right->right = new Node(6);
    root->right->left->left = new Node(7);
    root->right->left->right = new Node(8);

    BottomMostView(root);
    return 0;
}

Output

7 5 8 6

JAVA

import java.io.*;
import java.lang.*;
import java.util.*;

class Main{

// Class to create a node
// having an integer value, data
// and two pointers
// to store the references of the
// left and right children
static class Node
{
	
	int data;

	// variable to store horizontal 
    // distance of a node 
	int hd;

	Node left, right;

	public Node(int key)
	{
		data = key;
		hd = Integer.MAX_VALUE;
		left = right = null;
	}
}

// Helper method to recursively
// find a tree's bottom view.
static void findBottomViewUtil(Node root, int curr, int hd,
								TreeMap<Integer, int[]> m)
{
	
	// Base case
	if (root == null)
		return;

    // if for some hd
    // there is no node present,
    // then insert it into the map
	if (!m.containsKey(hd))
	{
		m.put(hd, new int[]{ root.data, curr });
	}
	
	// case to handle the situation
    // having more than one nodes at a 
    // certain hd 
	else
	{
		int[] p = m.get(hd);
		if (p[1] <= curr)
		{
			p[1] = curr;
			p[0] = root.data;
		}
		m.put(hd, p);
	}

	// recursively find bottom-most node
    // in the left subtree 
	findBottomViewUtil(root.left, curr + 1,
						hd - 1, m);

	// recursively find bottom-most node
    // in the right subtree 
	findBottomViewUtil(root.right, curr + 1,
						hd + 1, m);
}

// method that takes the node
// of a tree as its parameter
// and print the tree's bottom view.
static void BottomMostView(Node root)
{

    // create a map
    // for storing the
    // hd, height and data of the nodes
	TreeMap<Integer, int[]> m = new TreeMap<>();

	findBottomViewUtil(root, 0, 0, m);

    // the map containing the bottom-most nodes
    // returned by the function
    // findBottomView()
	for(int val[] : m.values())
	{
		System.out.print(val[0] + " ");
	}
}

// Driver Code
public static void main(String[] args)
{
    Node root = new Node(1);
	root.left = new Node(2);
	root.right = new Node(3);
	root.right.left = new Node(5);
	root.right.right = new Node(6);
	root.right.left.left = new Node(7);
	root.right.left.right = new Node(8);

	BottomMostView(root);
}
}

Output

7 5 8 6

Python

# Class to create a node
# having an integer value, data
# and two pointers
# to store the references of the
# left and right children
class Node:
    
    def __init__(self, key = None,
                    left = None,
                    right = None):
                        
        self.data = key
        self.left = left
        self.right = right
        
def BottomMostView(root):
    
    # create a dictionary
    # for storing the
    # hd, height and data of the nodes
    d = dict()
    
    findBottomViewUtil(root, d, 0, 0)
    
    # Iterate over the dictionary
    # to print the bottom most nodes of the tree
    for i in sorted(d.keys()):
        print(d[i][0], end = " ")

def findBottomViewUtil(root, d, hd, level):
    
    # Base case
    if root is None:
        return
    
    # if for some hd
    # there is no node present,
    # then insert it into the dictionary
    if hd in d:
        if level >= d[hd][1]:
            d[hd] = [root.data, level]
    else:
        d[hd] = [root.data, level]
        
    # recursively find bottom-most node
    # in the left subtree 
    findBottomViewUtil(root.left, d, hd - 1,
                                level + 1)
    
    
    # recursively find bottom-most node
    # in the right subtree 
    findBottomViewUtil(root.right, d, hd + 1,
                                    level + 1)

# Driver Code
if __name__ == '__main__':
    
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.right.left = Node(5)
    root.right.right = Node(6)
    root.right.left.left = Node(7)
    root.right.left.right = Node(8)
    
    BottomMostView(root)

Output

7 5 8 6

Complexity Analysis

Time Complexity : O(n), where ‘n’ is the number of nodes in the binary tree. Space Complexity: O(n), where ‘n’ is the number of nodes in the binary tree as in the worst case, a queue of the size n will be used.

Wrapping Up!

In this article, we have learned an amazing concept of Binary Trees. Binary Tree is one of the most important data structures and is usually asked in the top interview questions as well. “Bottom View of a Tree” is a popular as well as a very important problem that has been asked in various interview questions. In this article, we have included proper diagrams of trees for a better understanding for you. We also learned about what is level-order traversal and how it will be beneficial over other traversals i.e., inorder traversal, preorder traversal, and post-order traversal in such kinds of problems. We also discussed two well-explained approaches along with some suitable examples to solve this problem:

Using Queue
Using Recursion and Map

We also covered in detail how both of the approaches work and what is the significance of both of them respectively. Discussed their time complexity as well as space complexity along with a proper explanation. Different programmers prefer different languages for coding. So, we made sure that all our readers can refer to this article. That’s why, this article also contains well-explained codes for both the approaches in the three most popular languages which are c++, Java, and python along with their respective outputs attached to the article for a better understanding of a wide range of our readers. We sincerely hope that this article has walked you through some deep and important concepts of Binary Trees and how we should approach such kinds of problems. We surely wish you to keep up your practice and crack all the questions easily. With this, we are wrapping up this article. Happy Learning!

People are also reading:

Bottom View of a Binary Tree