A general approach to level order traversal questions in Java
This post is a compilation of some level order traversal questions.\n1. Binary Tree Level Order Traversal\n2. Binary Tree Level Order Traversal II\n3. Binary Tr
This post is a compilation of some level order traversal questions.\n1. Binary Tree Level Order Traversal\n2. Binary Tree Level Order Traversal II\n3. Binary Tree Zigzag Level Order Traversal\n4. Average of Levels in Binary Tree\n5. Binary Tree Right Side View\n6. Find Largest Value in Each Tree Row\n7. Populating Next Right Pointers in Each Node\n\n<br>\n 1. <b>Binary Tree Level Order Traversal:</b>\n \nhttps://leetcode.com/problems/binary-tree-level-order-traversal/description/\n\n```\nclass Solution {\n    public List<List<Integer>> levelOrder(TreeNode root) {\n        List<List<Integer>> ans=new ArrayList<>();\n        compute(ans,root,0);\n        return ans;\n    }\n    \n    public void compute(List<List<Integer>> ans,TreeNode curr,int level)\n    {\n        if(curr==null) return;\n        \n        if(ans.size()==level) \n            ans.add(new ArrayList<Integer>());\n        \n        ans.get(level).add(curr.val);\n        \n        compute(ans,curr.left,level+1);\n        compute(ans,curr.right,level+1);\n    }\n}\n```\n\n<br>\n2. <b>Binary Tree Level Order Traversal II</b>\n\nhttps://leetcode.com/problems/binary-tree-level-order-traversal-ii/description/\n```\nclass Solution {\n    public List<List<Integer>> levelOrderBottom(TreeNode root) {\n        List<List<Integer>> ans=new ArrayList<>();\n        compute(ans,root,0);\n        return ans;\n    }\n    \n    public void compute(List<List<Integer>> ans,TreeNode curr,int level)\n    {\n        if(curr==null) return;\n        \n        if(ans.size()==level) \n            ans.add(0,new ArrayList<Integer>());\n        \n        ans.get(ans.size()-level-1).add(curr.val);\n        \n        compute(ans,curr.left,level+1);\n        compute(ans,curr.right,level+1);\n    }\n}\n```\n<br>\n3. <b>Binary Tree Zigzag Level Order Traversal</b>\n\nhttps://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/description/\n```\nclass Solution {\n\n    public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {\n        List<List<Integer>> ans = new ArrayList<>();\n        compute(root, ans, 0);\n        return ans;\n    }\n\n    private static void compute(TreeNode curr, List<List<Integer>> ans, int level) {\n        if (curr == null) return;\n\n        if (ans.size() == level) \n            ans.add(new ArrayList<Integer>());\n\n        if (level % 2 == 0) \n            ans.get(level).add(curr.val);\n        else \n            ans.get(level).add(0, curr.val);\n\n        compute(curr.left, ans, level + 1);\n        compute(curr.right, ans, level + 1);\n    }\n}\n```\n<br>\n4. <b>Average of Levels in Binary Tree</b>\n\nhttps://leetcode.com/problems/average-of-levels-in-binary-tree/description/\n```\nclass Solution {\n    public List<Double> averageOfLevels(TreeNode root) {\n        //Sum stores the sum of each level\n        //Count stores the number of nodes at each level\n        List<Double> sum=new ArrayList<>();\n        List<Double> count=new ArrayList<>();\n        compute(sum,count,root,0);\n        for(int i=0;i<sum.size();i++)\n            sum.set(i,sum.get(i)/count.get(i));\n        return sum;\n        \n    }\n    \n    public void compute(List<Double> sum,List<Double> count,TreeNode curr,int level)\n    {\n        if(curr==null) return;\n        \n        if(sum.size()==level) \n        {\n            sum.add(0.0);\n            count.add(0.0);\n        }   \n        \n        sum.set(level,sum.get(level)+(double)curr.val);\n        count.set(level,count.get(level)+1);\n        \n        compute(sum,count,curr.left,level+1);\n        compute(sum,count,curr.right,level+1);\n    }\n}\n```\n<br>\n5. <b>Binary Tree Right Side View</b>\n\nhttps://leetcode.com/problems/binary-tree-right-side-view/description/\n```\n\npublic class Solution {\n    public List<Integer> rightSideView(TreeNode root) {\n        List<Integer> ans = new ArrayList<Integer>();\n        compute(root, ans, 0);\n        return ans;\n    }\n    \n    public void compute(TreeNode curr, List<Integer> ans, int level){\n        if(curr == null) return;\n      \n        if(ans.size()==level)\n            ans.add(curr.val);\n        \n        compute(curr.right, ans, level + 1);\n        compute(curr.left, ans, level + 1);\n        \n    }\n}\n```\n<br>\n6. <b>Find Largest Value in Each Tree Row</b>\n\nhttps://leetcode.com/problems/find-largest-value-in-each-tree-row/description/\n```\nclass Solution {\n    public List<Integer> largestValues(TreeNode root) {\n        List<Integer> ans=new ArrayList<>();\n        compute(root,ans,0);\n        return ans;\n    }\n    \n    public void compute(TreeNode curr,List<Integer> ans,int level)\n    {\n        if(curr==null) return;\n        \n        if(ans.size()==level)\n            ans.add(curr.val);\n        \n        if(curr.val>ans.get(level))\n            ans.set(level,curr.val);\n        \n        compute(curr.left,ans,level+1);\n        compute(curr.right,ans,level+1);\n    }\n}\n```\n<br>\n7. <b>Populating Next Right Pointers in Each Node</b>\n\nhttps://leetcode.com/problems/populating-next-right-pointers-in-each-node/description/\n```\npublic class Solution {\n    public void connect(TreeLinkNode root) {\n        compute(root);\n    }\n    \n    public void compute(TreeLinkNode curr)\n    {\n        if(curr==null || curr.left==null) return;\n        \n        curr.left.next=curr.right;\n        if(curr.next!=null)\n            curr.right.next=curr.next.left;\n        \n        compute(curr.left);\n        compute(curr.right);\n    }\n}\n```
[]