Bottom View of Tree

Bottom View of Tree

  October 04, 2017    

---

 A node x is there in output if x is the bottom most node at its horizontal distance from root. Horizontal distance of left child of a node x is equal to horizontal distance of x minus 1, and that of right child is horizontal distance of x plus 1.

Idea is to use Level Order Traversal and every time we add hd with node data into map .
So that the order is maintained.


Code:

 public void bottomView(Node root)
    {
        if(root==null)
        return;
        Queue<Node> q=new LinkedList<Node>();
        Map<Integer,Integer> map=new TreeMap<Integer,Integer>();
        root.hd=0;
        q.add(root);
        while(!q.isEmpty())
        {
          //  System.out.print("in  ");
            Node t=q.remove();
            map.put(t.hd,t.data); 
            if(t.left!=null)
           { 
                t.left.hd=t.hd-1;
               q.add(t.left);
               
           }   
            if(t.right!=null)
            {
                
                t.right.hd=t.hd+1;
                q.add(t.right);
            }
        }
        for(Map.Entry<Integer,Integer> m:map.entrySet())
        {
            System.out.print(m.getValue()+" ");
        }
    }