Wednesday, October 15, 2014

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


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

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)
    ArrayList<ArrayList<TreeNode>> outerList  = new ArrayList<ArrayList<TreeNode>>();
    outerList.add(new ArrayList<TreeNode>());
    for(int i=0;i<outerList.size();i++){
ArrayList<TreeNode> currentLevelList = outerList.get(i) ;
    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){
       public static void main(String[] args) {
        /* Create following Binary Tree
            /    \
          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


No comments:

Post a Comment