Untitled

class Tree
{
     public ArrayList<Integer> diagonal(Node root)
      {
          Deque<Node> q = new ArrayDeque<>();
          q.addLast(root);
          ArrayList<Integer> ans = new ArrayList<>();
          while(!q.isEmpty())
          {
              Node tmp = q.removeFirst();
              while(tmp!=null)
                {
                    ans.add(tmp.data);
                    if(tmp.left!=null)
                        q.addLast(tmp.left);
                    tmp=tmp.right;
                }
          }
          return ans;
      }
}
class Tree2
{
     public ArrayList<Integer> diagonal(Node root)
      {
          ArrayList<Integer> ans = new ArrayList<>();
          Map<Integer,List<Integer>> hm = new LinkedHashMap<>();
           int mx=getMax(root,hm,0,0);
           //System.out.println(hm);
         for(int i : hm.keySet())
        {      List<Integer> tmp = hm.get(i);
              for(int j=0;j<tmp.size();j++)
                ans.add(tmp.get(j));
          }
          return ans;
      }
      int getMax(Node root , Map<Integer,List<Integer>> hm , int d, int l)
      {
          if(root==null)
            return l-d;
          if(hm.containsKey(l-d))
          {
              hm.get(l-d).add(root.data);
          }
          else
          {
              List<Integer> tmp = new ArrayList<>();
              tmp.add(root.data);
              hm.put(l-d,tmp);
          }
          return Math.max(getMax(root.left,hm,d-1,l+1),getMax(root.right,hm,d+1,l+1));
      }
}