Print the Bottom View of the Binary Tree. | Algorithms

Print the Bottom View of the Binary Tree. | Algorithms
Objec­tive: - Given a binary tree, print it in Bot­tom View of it.
What is Bot­tom View: Bot­tom view means when you look the tree from the bot­tom the nodes you will see will be called the bot­tom view of the tree. See the exam­ple below.

8,4, 9, 5, 3, 7 is the bot­tom view of the given binary tree.

This Approach is quite sim­i­lar to the - Print the Binary Tree in Ver­ti­cal Order Path.and Print The Top View of a Binary Tree. Just mod­i­fied the code so that it will print only the last ele­ment it will encounter in the ver­ti­cal order. That will be the bot­tom view.

How will you know that you are vis­it­ing the last node at every level(Vertically)?

• Take a vari­able called level, when­ever you go left, do level++ AND when­ever you go right do level–.
• With step above we have sep­a­rated out the lev­els vertically.

• Now you need to store the ele­ments of each level, so cre­ate a TreeMap and the (key,value) pair will be (level,element at that level).
• Now all we need to do the level order tra­ver­sal and store only recent vis­ited node at each level(vertically), this way you will be stor­ing only the last ele­ment at each level.
• We will use sim­ple queue tech­nique for level order tra­ver­sal or BFS.
• we will cre­ate a class QueuePack, this will store the objects con­tain­ing node and its level.
• At the end tra­verse through TreeMap and print all the val­ues in it, it will be the bot­tom view of a tree.

public class BottomViewOfBT {
public static TreeMap<Integer, Integer> ht = new TreeMap<>();;

public static void bottomView(Node root, int level) {
if (root == null)
return;
// create a queue for level order traversal
Queue<QueuePack> queue = new LinkedList<>();
// add root with level 0 (create a queue item pack)
queue.add(new QueuePack(level, root));
while (!queue.isEmpty()) {
QueuePack q = queue.remove();
// take out the items from the package
Node tnode = q.tnode;
int lvl = q.level;

// keep updating the Map so that it will have the last entry from
// each level(vertically) and that will the bottom view of the tree
ht.put(lvl, tnode.data);

// add the left and right children of visiting nodes to the queue
if (tnode.left != null) {
queue.add(new QueuePack(lvl - 1, tnode.left));
}
if (tnode.right != null) {
queue.add(new QueuePack(lvl + 1, tnode.right));
}
}

}

public static void display() { // print the bottom view.
Set<Integer> keys = ht.keySet();
for (Integer key : keys) {
System.out.print(ht.get(key) + " ");
}

}
}

class Node {
int data;
Node left;
Node right;

public Node(int data) {
this.data = data;
left = null;
right = null;
}
}

// this class' represents the items stored in queue (used for level order
// traversal). Objects will store the nodes and its level
class QueuePack {
int level;
Node tnode;

public QueuePack(int level, Node tnode) {
this.level = level;
this.tnode = tnode;
}
}
http://www.geeksforgeeks.org/bottom-view-binary-tree/

If there are multiple bottom-most nodes for a horizontal distance from root, then print the later one in level traversal. For example, in the below diagram, 3 and 4 are both the bottom-most nodes at horizontal distance 0, we need to print 4.

                   
                      20
                    /    \
                  8       22
                /   \    /   \
              5      3 4     25
                    / \      
                  10    14 

For the above tree the output should be 5, 10, 4, 14, 25.

class TreeNode

{

    int data; //data of the node

    int hd; //horizontal distance of the node

    TreeNode left, right; //left and right references

 

    // Constructor of tree node

    public TreeNode(int key)

    {

        data = key;

        hd = Integer.MAX_VALUE;

        left = right = null;

    }

}

 

//Tree class

class Tree

{

    TreeNode root; //root node of tree

 

    // Default constructor

    public Tree() {}

 

    // Parameterized tree constructor

    public Tree(TreeNode node)

    {

        root = node;

    }

 

    // Method that prints the bottom view.

    public void bottomView()

    {

        if (root == null)

            return;

 

        // Initialize a variable 'hd' with 0 for the root element.

        int hd = 0;

 

        // TreeMap which stores key value pair sorted on key value

        Map<Integer, Integer> map = new TreeMap<>();

 

         // Queue to store tree nodes in level order traversal

        Queue<TreeNode> queue = new LinkedList<TreeNode>();

 

        // Assign initialized horizontal distance value to root

        // node and add it to the queue.

        root.hd = hd;

        queue.add(root);

 

        // Loop until the queue is empty (standard level order loop)

        while (!queue.isEmpty())

        {

            TreeNode temp = queue.remove();

 

            // Extract the horizontal distance value from the

            // dequeued tree node.

            hd = temp.hd;

 

            // Put the dequeued tree node to TreeMap having key

            // as horizontal distance. Every time we find a node

            // having same horizontal distance we need to replace

            // the data in the map.

            map.put(hd, temp.data);

 

            // If the dequeued node has a left child add it to the

            // queue with a horizontal distance hd-1.

            if (temp.left != null)

            {

                temp.left.hd = hd-1;

                queue.add(temp.left);

            }

            // If the dequeued node has a left child add it to the

            // queue with a horizontal distance hd+1.

            if (temp.right != null)

            {

                temp.right.hd = hd+1;

                queue.add(temp.right);

            }

        }

 

        // Extract the entries of map into a set to traverse

        // an iterator over that.

        Set<Entry<Integer, Integer>> set = map.entrySet();

 

        // Make an iterator

        Iterator<Entry<Integer, Integer>> iterator = set.iterator();

 

        // Traverse the map elements using the iterator.

        while (iterator.hasNext())

        {

            Map.Entry<Integer, Integer> me = iterator.next();

            System.out.print(me.getValue()+" ");

        }

    }

}

Exercise: Extend the above solution to print all bottommost nodes at a horizontal distance if there are multiple bottommost nodes. For the above second example, the output should be 5 10 3 4 14 25.

http://www.ideserve.co.in/learn/bottom-view-of-a-binary-tree-using-level-order-traversal
Read full article from Print the Bottom View of the Binary Tree. | Algorithms