Print bottom view of a binary tree using level order traversal

Given a binary tree, print the values of nodes that would appear when the tree is viewed from bottom. Print the node values starting from left-most end. A node will be in the bottom-view if it is the bottommost node at its horizontal distance from the root. Horizontal distance of root from itself is 0. Horizontal distance of right child of root node is 1 and horizontal distance of left child of root node is -1.

Horizontal distance of node 'n' from root = horizontal distance of its parent from root + 1, if node 'n' is right child of its parent
Horizontal distance of node 'n' from root = horizontal distance of its parent from root - 1, if node 'n' is left child of its parent

If more than one nodes are at the same horizontal distance and are the bottommost nodes for  that horizontal distance, then you can choose to include either of the nodes in the bottom view.

example -
    For the following tree:
                1
        2                3
    4        5        6        7

Horizontal distance of 1 = +0
Horizontal distance of 2 = -1
Horizontal distance of 3 = +1
Horizontal distance of 4 = -2
Horizontal distance of 5 = +0
Horizontal distance of 6 = +0
Horizontal distance of 7 = +2    

and the bottom view would be 4, 2, 6, 3, 7.

Please note that though there are three nodes(nodes 1,5,6) with horizontal distance of 0, only node 6 is in bottom view because it is at the bottom-most level of all three nodes. Note that you could have chosen to keep node 5 instead of node 6 in bottom view since it is also at the bottom-most layer.

For the following tree:

                1
           2          3
        4    5     6     7
          8 9        10    11
          
Horizontal distance of 1 = +0
Horizontal distance of 2 = -1
Horizontal distance of 3 = +1
Horizontal distance of 4 = -2
Horizontal distance of 5 = +0
Horizontal distance of 6 = +0
Horizontal distance of 7 = +2    
Horizontal distance of 8 = -1 (right child of 4)
Horizontal distance of 9 = -1 (left child of 5)
Horizontal distance of 10 = +1 (right child of 6)
Horizontal distance of 11 = +3 (right child of 7)     

and the bottom view would be 4, 9, 6, 10, 7, 11


Video coming soon!



Subscribe for more updates


Algorithm/Insights

To solve this problem we use a simple idea of using level order traversal with slight modification. The modification is that while doing the level order traversal, we keep track of the horizontal distance(from the root node) of the current node being visited. During this level-order traversal, we update the treeMap(a modified hashMap which keeps entries sorted by key) with node's horizontal distance as key and value as current node's value if the node being visited is the bottommost node seen at its horizontal distance.  And because we are doing a level order traversal starting from top-most level and ending at bottom-most level, all we need to do keep updating the treeMap with (nodeValue, horizontalDistance) at each node's visit. Notice that, if there are multiple nodes at the same horizontal distance, then bottom most node of these will overwrite the entry of other nodes in the viewMap.

The algorithm is as following -
1. Initialize viewMap to an empty treeMap.
2. Call fillUpViewMap function with arguments as (root = root, viewMap = viewMap)
3. If root is null, do nothing and return.
4. If root is not null then - (following steps basically do a level order traversal of the given tree)
    4a. Add the tuple(currentNode = rootNode, horizontalDistance = 0) to the queue - 'nodeQueue'.
    4b. while 'nodeQueue' is not empty    
        - remove first tuple(currentNode, horizontalDistance) from 'nodeQueue'
        - update the viewMap with tuple (key = horizontalDistance, value = currentNode's value). If viewMap already contains an entry with 'horizontalDistance' as key, then we overwrite the previous entry with this current entry - (key = horizontalDistance, value = currentNode's value).
        - if left child of currentNode is not null, then  we add tuple(currentNode.left, horizontalDistance - 1) to 'nodeQueue'
        - if right child of currentNode is not null, then  we add tuple(currentNode.right, horizontalDistance + 1) to 'nodeQueue'
5. After completion of step #4, our viewMap is completely updated with keys(horizontal distance) and values(nodeValues) in sorted order of keys. All we need to do is print out the values in this viewMap to get the bottomView.     
    
Please checkout code snippet and algorithm visualization section for more details of the algorithm.


Algorithm Visualization




Code Snippet

			
package com.ideserve.questions.nilesh;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Given a binary tree, print the values of nodes which would be present in bottom of view of binary tree. A node will be in the bottom-view if it is the bottommost node at its horizontal distance from the root. 
 * @author Nilesh
 */

public class BottomViewOfBinaryTreeLevelOrder {

    class TreeNode
    {
        TreeNode left;
        TreeNode right;
        int val;
    
        public TreeNode(int x)
        {
            this.val = x;
        }
    }
    
    TreeNode root;
    
    class QueueEntry
    {
        TreeNode node;
        int horizontalDistFromRoot;
        public QueueEntry (TreeNode node, int distance)
        {
            this.node = node;
            this.horizontalDistFromRoot = distance;
        }
    }

    /*
                            1
                      2            3
                  4      5       6    7
                    8  9          10    11
    */

    private TreeNode createTree()
    {
        this.root = new TreeNode(1);
        TreeNode n1   = new TreeNode(2);
        TreeNode n2   = new TreeNode(3);
        TreeNode n3   = new TreeNode(4);
        TreeNode n4   = new TreeNode(5);
        TreeNode n5   = new TreeNode(6);
        TreeNode n6   = new TreeNode(7);
        TreeNode n7   = new TreeNode(8);
        TreeNode n8   = new TreeNode(9);
        TreeNode n9   = new TreeNode(10);
        TreeNode n10   = new TreeNode(11);
        
        root.left  = n1;
        root.right = n2;
        
        n1.left  = n3;
        n1.right = n4;
        
        n2.left  = n5;
        n2.right = n6;
        
        n3.right = n7;
        
        n4.left = n8;
        
        n5.right = n9;
        
        n6.right = n10;
        
        return root;
    }

    
    private void fillUpViewMap(TreeNode root, Map viewMap)
    {
        if (root == null) return;
        
        LinkedList<QueueEntry> queue = new LinkedList();
        queue.add(new QueueEntry(root, 0));
        
        while (!queue.isEmpty())
        {
            QueueEntry currentNode = queue.remove();
            viewMap.put(currentNode.horizontalDistFromRoot, currentNode.node.val);

            // we don't add null nodes into the queue
            if (currentNode.node.left != null)
                queue.add(new QueueEntry(currentNode.node.left, currentNode.horizontalDistFromRoot - 1));

            if (currentNode.node.right != null)
                queue.add(new QueueEntry(currentNode.node.right, currentNode.horizontalDistFromRoot + 1));
        }
    }
    

    private void printBottomView()
    {
        Map<Integer, Integer> viewMap = new TreeMap<>();

        fillUpViewMap(root, viewMap);

        // print map entries to print the Bottom view
        Iterator<Entry<Integer, Integer>> iterator = viewMap.entrySet().iterator();

        while (iterator.hasNext())
        {
            Entry<Integer, Integer> nodeEntry = iterator.next();
            System.out.print("  " + nodeEntry.getValue());
        }
    }
    
    
    public static void main(String[] args)
    {
        BottomViewOfBinaryTreeLevelOrder tree = new BottomViewOfBinaryTreeLevelOrder();
        tree.createTree();
        tree.printBottomView();
    }
    
}
		

Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(n)


Contribution

  • Sincere thanks from IDeserve community to Nilesh More for compiling current post.


    Nilesh More