Java

Binary Tree in Java – 23: Print Top View of Binary Tree



Source Code:

Solution:
– We’ll take verticle height of each node. For root it’s 0 & if height – 1, if we’re going right & height + 1, if we’re going left
– Take Queue & add root node into it
– Now one by one remove item from queue & add into Tree map based on height as key. Add only key is not present in map
– Do it until queue is empty
– At last, print all values of map
– Time Complexity: O(n)
– Space Complexity: O(n)

Please…

Similar Posts

20 thoughts on “Binary Tree in Java – 23: Print Top View of Binary Tree
  1. hi sir, Can i solve in this manner ? It is giving correct answer. Please suggest is it a right approach ?

    static TreeMap<Integer,Integer> map=new TreeMap<Integer,Integer>();
    static void getTopView(Node root,int level){

    if (root==null) {
    return ;
    }

    if(!map.containsKey(level)){
    map.put(level,root.data);
    }
    getTopView(root.right,level+1);
    getTopView(root.left,level-1);

    }

  2. Sir, I have tried the way from your video of vertical order traversal.
    I remove the code where we have the key in the map,the idea is that to only get numbers whose level is not considered but is wrong I am not able to understand why?
    public void getVerticalOrder(Node node, int hd, TreeMap<Integer, ArrayList<Integer>> m) {
    if (node == null) {
    return;
    }

    if (m.get(hd) == null) {
    ArrayList<Integer> l = new ArrayList<Integer>();
    l.add(node.data);
    m.put(hd, l);
    }
    getVerticalOrder(node.left, hd – 1, m);
    getVerticalOrder(node.right, hd + 1, m);

  3. This can also work..

    Set<Integer> a= new HashSet<>();

    void TopView(Node root, int level){

    if(root==null)return;

    if(!a.contains(level))

    {

    System.out.print(" "+root.data+" ");

    a.add(level);

    }

    TopView(root.left, level-1);

    TopView(root.right, level+1);

    }

  4. Plzz help…
    This approach does not require a queue. Here we use the two variables, one for vertical distance of current node from the root and another for the depth of the current node from the root. We use the vertical distance for indexing. If one node with the same vertical distance comes again, we check if depth of new node is lower or higher with respect to the current node with same vertical distance in the map. If depth of new node is lower, then we replace it.

    This is from geeksforgeeks..
    Why do we need to check the level of the node..Cant we just put the first element with the same horizontal distance in the top view of the tree..
    Plzzzzzzzzzz HElppppppppppppp

Leave a Reply

Your email address will not be published. Required fields are marked *