A tree is a nonlinear data structure that is widely used. A tree, unlike other linear data structures such as an array, stack, queue, or linked list, represents a hierarchical structure. A binary tree is a tree data structure made up of nodes (left and right nodes), each of which has at most two children. The tree begins with a single node, which is referred to as the root or bottom view of the Binary Tree

Each node in the tree contains the following:

1. Data

2. Pointer to the left child

3. Pointer to the right child

              2

                    /    \

                  8       32

                /   \      \

              3      5      23

                    / \      

                  1    12

The nodes that do not have a left and right child are called leaf nodes.For example, in the above tree, Nodes with data 3, 1, 12 and 23 are the leaf nodes.

The bottom view of a binary tree refers to the nodes at the bottom of the tree when measured horizontally. The nodes that came into sight when viewing the tree from bottom direction forms the bottom view of the binary tree.

The horizontal distance between nodes in a binary tree is defined as follows:

1. The root's horizontal distance is equal to zero.

2. A left child's horizontal distance equals its parent's horizontal distance minus one.For example the horizontal distance for node 8 will be 0 - 1 = -1 (Note that 0 is the horizontal distance for the root node).

3. A right child's horizontal distance equals its parent's horizontal distance plus one.

For example the horizontal distance for node with data 32 will be 0 + 1 (Note that 0 is the horizontal distance for the root node).

The following illustration shows the horizontal distances and the bottom view of a binary tree.

                      2

                    /    \

                  8       32

                /   \      \

              3      5      23

                    / \      

                  1    12

For the above tree the bottom view of the tree is 3, 1, 5, 12, 23.

For a particular horizontal distance if there are multiple bottom most nodes, then print the later one according to the level order traversal. For example in the below binary tree the output should be 3 1 6 12 23

20

        /       \

      8         32

    /   \       /    \

  3      5    6     23

        /  \

      1   12

Using Queue

A queue can be used to find the bottom view of the binary tree. The idea is to use level order traversal of the binary tree. The Level Order Traversal is the algorithm to process all nodes of a tree by traversing through depth, first the root, then the child of the root, It is also known as the breadth first traversal of the binary tree.

Algorithm

1. For level order traversal, we put tree nodes in a queue.

2. Begin with the root node's horizontal distance(h) 0 and add a left child to the queue with a horizontal distance of h-1 and a right child with a horizontal distance of h+1.

3. Use a Map to store key-value pairs that are ordered by key.

4. Put the node data for the horizontal distance as the key, every time we encounter a new horizontal distance or an existing horizontal distance.

5. For the bottom-most element, the nodes of a specific horizontal distance are present on the map as the first time it will be added to the map, the second time it will replace the value.

Let’s the function implement the bottom view of a binary tree - 

void bottomView(Node *root)

{

    if (root == NULL)

        return;

   // h is for horizontal distance

    int h = 0;

   //  Map to store key-value pairs that are ordered by key.

    map<int, int> m;

  // queue is used for level order traversal

  queue<Node *> q;

    root->h = h;

    q.push(root);  

    while (!q.empty())

    {

        Node *tempNode = q.front();

        q.pop();   

        h = tempNode->h;

        m[h] = tempNode->data;

        if (tempNode->left != NULL) {

            tempNode->left->h = h-1;

            q.push(tempNode->left);

        } else if (tempNode->right != NULL) {

            tempNode->right->h = h+1;

            q.push(tempNode->right);

        }

    }

    for (auto i = m.begin(); i != m.end(); ++i)

        cout << i->second << " ";

}

Using HashMap() 

A HashMap can also be used to find out the bottom view of a binary tree, the key of the map will be the horizontal distance and value will be a pair(x, y) where x is the value of the node and y is the height of the node.

The idea is to calculate the horizontal distance between each node using pre-order traversal. If the node is the first to have a certain horizontal distance, add it to the result. If a node exists in the result for a certain edit distance, only replace it with the present node if the present node is higher in level than the previously inserted node.

Algorithm

1. Make a map using the horizontal distance as the key and a pair(x, y) as the value, where a represents the node's value and b represents the node's height.

2. Traverse the tree in a pre-ordered fashion.

3. Insert the current node into the map if it's the first one we've seen at a horizontal distance of h.

4. If not, compare the new node's height to the old one in the map, then update the map if the new node's height is larger.

Lets’ see the code implementation - 

#include <bits/stdc++.h>

using namespace std;

struct Node

{

    int data;

    int h;

    Node * l, * r;

    Node(int val) {

        data = val;

        h = INT_MAX;

        l = r = NULL;

    }

};

void bottomView(Node * TreeRoot, int curr, int h, map <int, pair <int, int>> & m)

{

    if (TreeRoot == NULL)

        return;

    // Add a node to the map if there isn't one for a specific horizontal distance.

    if (m.find(h) == m.end())

        m[h] = make_pair(TreeRoot -> data, curr);

    else {

        pair < int, int > p = m[h];

        if (p.second <= curr)

        {

            m[h].second = curr;

            m[h].first = TreeRoot -> data;

        }

    }

    bottomView(TreeRoot -> l, curr + 1, h - 1, m);

    bottomView(TreeRoot -> r, curr + 1, h + 1, m);

}

void printBottomView(Node * TreeRoot)

{

    map < int, pair < int, int > > m;

    bottomView(TreeRoot, 0, 0, m);

    for (auto it = m.begin(); it != m.end(); ++it)

    {

        pair < int, int > p = it -> second;

        cout << p.first << " ";

    }

}

int main()

{

    Node * TreeRoot = new Node(2);

    TreeRoot -> l = new Node(10);

    TreeRoot -> r = new Node(15);

    TreeRoot -> l -> r = new Node(22);

    TreeRoot -> r -> r = new Node(100);

    TreeRoot -> l -> r -> l = new Node(16);

    TreeRoot -> l -> r -> r = new Node(35);

    cout << " bottom view of binary tree: ";

    printBottomView(TreeRoot);

    return 0;

}