Print All Nodes Between Two Given Levels

Objective: Given a binary Tree and two levels, Print all the nodes between those.

Input: A Binary Tree and two levels.

Output: Print all the nodes between given levels.

Example:

Print All Nodes Between Two Given Levels
Print All Nodes Between Two Given Levels


Approach:

  • The solution of this problem is very simple, Do level order traversal and in recursive calls first add the right child and then left child.
  • Take a global variable say, currLevel which will store the current level while doing Level Order traversal.
  • Print only nodes between given levels.

Read this solution “ Level Order Traversal, Print each level in separate line” and implement the above approach.

Complete Code:

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
public class NodesBwTwoGivenLevels {
public static int currLevel = 1;
public void levelOrderQueue(Node root, int low, int high){
Queue q = new LinkedList();
int levelNodes =0;
if(root==null) return;
q.add(root);
while(!q.isEmpty()){
levelNodes = q.size();
while(levelNodes>0){
Node n = (Node)q.remove();
if(currLevel>=low && currLevel<=high){
System.out.print(" " + n.data);
}
if(n.left!=null) q.add(n.left);
if(n.right!=null) q.add(n.right);
levelNodes;
}
if(currLevel>=low && currLevel<=high){
System.out.println("");
}
currLevel++;
}
}
public static void main (String[] args) throws java.lang.Exception
{
Node root = new Node(5);
root.left = new Node(10);
root.right = new Node(15);
root.left.left = new Node(20);
root.left.right = new Node(25);
root.right.left = new Node(30);
root.right.right = new Node(35);
root.left.right.left = new Node(40);
root.left.right.right = new Node(45);
root.left.right.left.left = new Node(50);
NodesBwTwoGivenLevels i = new NodesBwTwoGivenLevels();
int low = 2;
int high = 3;
System.out.println("Print all nodes between nodes " + low + " and " + high);
i.levelOrderQueue(root,low,high);
}
}
class Node{
int data;
Node left;
Node right;
public Node(int data){
this.data = data;
this.left = null;
this.right =null;
}
}

Output:

Print all nodes between nodes 2 and 4
10 15
20 25 30 35
40 45