Print top view of a binary tree

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


Algorithm/Insights

The basic idea is to use modified pre-order traversal. In this modified pre-order traversal, we keep track of horizontal distance of the node being visited from the root. We also keep track of vertical level of that node(Vertical level of root would be 0 and its children would be 1). During this traversal, we update the treemap(a modified hashmap which keeps entries sorted by key) with node's horizontal distance as key and value as tuple (current node's value, current node's level) if the node being visited is the topmost node seen at its horizontal distance.
The algorithm is as following -
1. Initialize viewMap to an empty treeMap.
2. Call fillUpViewMap function with arguments as (currentNode = root, currLevel = 0, horizontalDistFromRoot = 0, viewMap = viewMap)
3. If currentNode is null, do nothing and return.
4. If currentNode is not null then
    4a. if there is an entry present in viewMap with key as  horizontalDistFromRoot, check if the node in that entry has level > currLevel. If this is not true, then we know that current node is the topmost node seen so far for its horizontal distance and therefore we update viewMap with key as horizontalDistFromRoot and value as tuple (current node's value, currLevel).
    4b. if there is not any entry present in viewMap with key as horizontalDistFromRoot, then we simply update viewMap with key as horizontalDistFromRoot and value as tuple (current node's value, currLevel).
    4c. Now that we are done with update of viewMap for this particular node, we make a recursive call fillUpViewMap(currentNode.left, currLevel+1, horizontalDistFromRoot-1, viewMap) to update viewMap for currentNode's left subtree.
    4d. We also make a recursive call fillUpViewMap(currentNode.right, currLevel+1, horizontalDistFromRoot+1, viewMap) to update viewMap for currentNode's right subtree.
5. After completion of step #4, our viewMap is completely updated with keys(horizontal distance) in sorted order. 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.


Algorithm Visualization




Code Snippet

			
package com.ideserve.questions.nilesh;

import java.util.Iterator;
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 TopViewOfBinaryTree {

    class TreeNode
    {
        TreeNode left;
        TreeNode right;
        int val;
    
        public TreeNode(int x)
        {
            this.val = x;
        }
    }
    
    TreeNode root;
    
    class MapEntry
    {
        int nodeValue;
        int nodeLevel;
        public MapEntry (int value, int level)
        {
            nodeValue = value;
            nodeLevel = level;
        }
    }

    /*
                            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 currentNode, int currLevel, int horizontalDistFromRoot, Map viewMap)
    {
        if (currentNode == null) return;
        
        MapEntry mapEntry = (MapEntry) viewMap.get(new Integer(horizontalDistFromRoot));
        
        if (mapEntry != null) // if node exists at same horizontal distance from root
        {
            // update the view map only if current node is at lower or equal level than already existing one
            if (currLevel <= mapEntry.nodeLevel)
            {
                MapEntry nodeEntry = new MapEntry(currentNode.val, currLevel);
                viewMap.put(horizontalDistFromRoot, nodeEntry);
            }
        }
        else // update viewMap with current node entry
        {
            MapEntry nodeEntry = new MapEntry(currentNode.val, currLevel);
            viewMap.put(horizontalDistFromRoot, nodeEntry);
        }
        
        // fill up view map for left sub-tree
        fillUpViewMap(currentNode.left, currLevel + 1, horizontalDistFromRoot - 1, viewMap);

        // fill up view map for right sub-tree
        fillUpViewMap(currentNode.right, currLevel + 1, horizontalDistFromRoot + 1, viewMap);
    }
    

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

        fillUpViewMap(root, 0, 0, viewMap);

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

        while (iterator.hasNext())
        {
            Entry<Integer, MapEntry> nodeEntry = iterator.next();
            System.out.print("  " + nodeEntry.getValue().nodeValue);
        }
    }
    
    
    public static void main(String[] args)
    {
        TopViewOfBinaryTree tree = new TopViewOfBinaryTree();
        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