Print all nodes between levels ‘m’ and ‘n’ in level in binary tree

Reference

http://www.geeksforgeeks.org/amazon-interview-experience-set-134-campus-sde/

Problem statement

Given ‘m’ and ‘n’ (m < n), print all nodes between levels ‘m’ and ‘n’ in level order.

My approach 

We will modify level order traversal a little bit. We will create a list of nodes on every level.

Create a master list (list of lists) indicating each level
Create a list to indicate 0th level and root to it.
Add this list into master list

Now traverse over master list i.e. traverse over every level one by one. 
Create new list for next level and add the children of node of current level into it.

Once all the levels are traversed print the sublists for required levels.

Java implementation

Also shared at

http://ideone.com/KhLv6E

import java.util.ArrayList;

class TreeNode {

  

    // data members

public int key;

    public TreeNode left;

    public TreeNode right;

  

    // Accessor methods

    public int key()        { return key; }

    public TreeNode left()  { return left; }

    public TreeNode right() { return right; }

  

    // Constructor

    public TreeNode(int key) { this.key = key; left = null; right = null; }

  

    // Methods to set left and right subtrees

    public void setLeft(TreeNode left)   { this.left = left; }

    public void setRight(TreeNode right) { this.right = right; }

    

    

    public static void printLevelOrderBetweenGivenLevels(TreeNode root,int fromLevel,int toLevel)

    {

    if(root!=null){

    ArrayList<ArrayList<TreeNode>> outerList  = new ArrayList<ArrayList<TreeNode>>();

    outerList.add(new ArrayList<TreeNode>());

    outerList.get(0).add(root);

    for(int i=0;i<outerList.size();i++){

ArrayList<TreeNode> currentLevelList = outerList.get(i) ;

    if(currentLevelList.size()>0){

    outerList.add(new ArrayList<TreeNode>());   // Create empty list for next level

    for(TreeNode node : currentLevelList){

    ArrayList<TreeNode> nextLevelList = outerList.get(i+1);

    if(node.left !=null) nextLevelList.add( node.left);

    if(node.right !=null) nextLevelList.add( node.right);

   

    }

    }

    }

   

    // Now print the list element for required levels

    for(int i=fromLevel; i<=toLevel && i<outerList.size() ;i++){

    ArrayList<TreeNode> currentLevelList = outerList.get(i);

    for(TreeNode node : currentLevelList){

    System.out.println(node.key);

    }

    }

    System.out.println("done");

    }

    }

    

    

       public static void main(String[] args) {

        /* Create following Binary Tree

              1

            /    \

          2        3

         / \      / \

        4   5    6   7

  

        */

        TreeNode root = new TreeNode(1);

        root.setLeft(new TreeNode(2));

        root.setRight(new TreeNode(3));

        root.left().setLeft(new TreeNode(4));

        root.left().setRight(new TreeNode(5));

        root.right().setLeft(new TreeNode(6));

        root.right().setRight(new TreeNode(7));

        // Levels start with zero

        TreeNode.printLevelOrderBetweenGivenLevels(root,2,4);

        

    }

}

Output

4
5
6
7
done