Print top 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 top. Print the node values starting from left-most end.
A node will be in the top-view if it is the topmost 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 topmost nodes for that horizontal distance, then you can choose to include either of the nodes in the top 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 top view would be 4, 2, 1, 3, 7.

Please note that though there are three nodes(nodes 1,5,6) with horizontal distance of 0, only node 1 is in top view because it is at the top-most level of all three nodes.

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 top view would be 4, 2, 1, 3, 7, 11


Video coming soon!



Subscribe for more updates


Preparing for interviews? IDeserve team is here to help.




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 topmost node seen at its horizontal distance.  And because we are doing a level order traversal starting from topmost level, all we need to do is update the treeMap with (nodeValue, horizontalDistance) when the node being visited is the first node for its horizontal distance.  

The algorithm is as following -
1. Initialize viewMap to a 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'
        - if viewMap does not contain an entry with 'horizontalDistance' as key, then that means this currentNode is the first and hence the topmost node at this 'horizontalDistance' and therefore, we update the viewMap with tuple(key = horizontalDistance, value = currentNode's value). If viewMap already contains an entry with 'horizontalDistance' as key, then we skip adding this node's value into the viewMap.
        - 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 topView.     
    
Please checkout code snippet and algorithm visualization section for more details of the algorithm.


Hone your coding skills!




AngryNerds Practice platform »

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 top of view of binary tree. A node will be in the top-view if it is the topmost node at its horizontal distance from the root. 
 * @author Nilesh
 */

 public class TopViewOfBinaryTreeLevelOrder {

    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();
            Integer mapEntry = (Integer)viewMap.get(currentNode.horizontalDistFromRoot);
            
            // if node exists in viewMap at this same horizontal distance 
            // then we cannot add this node into viewMap.
            if (mapEntry == null)
            {
                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 printTopView()
    {
        Map<Integer, Integer> viewMap = new TreeMap<>();

        fillUpViewMap(root, viewMap);

        // print map entries to print the top 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)
    {
        TopViewOfBinaryTreeLevelOrder tree = new TopViewOfBinaryTreeLevelOrder();
        tree.createTree();
        tree.printTopView();
    }
    
}
		

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

    Ninja Programmer