Print Each Level BST

PrintEachLevelBST.java

//print each tree level on it's own line
//Implementation: use BFS
//Used a BST here, but the function to print each level could be used on any Binary Tree


import java.util.Queue;
import java.util.LinkedList;
 
public class Main
{
  public static void main(String[] args)
  {
    BinaryTree tree = new BinaryTree();
    
    tree.add(20);
    tree.add(10);
    tree.add(30);
    tree.add(15);
    tree.add(25);
    tree.add(5);
    tree.add(35);
    tree.add(1);
    tree.add(6);
    tree.add(14);
    tree.add(16);
    tree.add(24);
    tree.add(26);
    tree.add(34);
    tree.add(36);
 
    
    tree.printEachLevel();
    
  }
}
 
public class TreeNode
{
  int data;
  TreeNode left;
  TreeNode right;
  
  public TreeNode(int d){
    data = d;
    left = null;
    right = null;
  }
  
}
 
public class BinaryTree
{
  TreeNode root;
  
  public BinaryTree(){
  	root = null;
  }
  
  public boolean add(int newData){
    if (root == null){
      root = new TreeNode(newData);
      return true;
    }
    else{
      TreeNode curr = root;
      while (true){
        if (curr.data == newData){
          return false;
        }
        else if (curr.data > newData){
          if (curr.left == null){
            curr.left = new TreeNode(newData);
            return true;
          }
          else{
            curr = curr.left;
          }
          
          
        }
        else{
          if (curr.right == null){
            curr.right = new TreeNode(newData);
            return true;
          }
          else{
            curr = curr.right;
          }
        }
      }
    }
    
  }
  
  
  public void printEachLevel(){
    if (root == null) return;
    
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    
    queue.add(root);
    
    int countCurrentLevel = 1;
    int countNextLevel = 0;
  
    TreeNode node = null;
    while (!queue.isEmpty()){
      node = queue.remove();
      System.out.print(String.format("%-4d", node.data));
      countCurrentLevel--;
      if (node.left != null){
      	queue.add(node.left);
      	countNextLevel++;
      }
      if (node.right != null){
      	queue.add(node.right);
      	countNextLevel++;
      }
      if (countCurrentLevel == 0){
        System.out.println();
        countCurrentLevel = countNextLevel;
        countNextLevel = 0;
      }
      
    }
    
  }
  
   
}

/*output:

20  
10  30  
5   15  25  35  
1   6   14  16  24  26  34  36  

*/




//Alternate, returning a list of lists

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<Integer> list= new ArrayList<Integer>();
        List<List<Integer>> listList= new ArrayList<List<Integer>>();
        
        if (root == null) return listList;
        
        Queue<TreeNode> treeQueue = new LinkedList<TreeNode>();
        
        int countCurrentLevel = 1;
        int countNextLevel = 0;
        
        treeQueue.add(root);
        while (!treeQueue.isEmpty()){
            TreeNode node = treeQueue.remove();
            list.add(node.val);
            countCurrentLevel--;
            if (node.left != null){
                treeQueue.add(node.left);
                countNextLevel++;
            }
            if (node.right != null){
                treeQueue.add(node.right);
                countNextLevel++;
            }
            
            if (countCurrentLevel == 0){
                listList.add(list);
                list = new ArrayList<Integer>();
                countCurrentLevel = countNextLevel;
                countNextLevel = 0;
            }
            
        }
        return listList;
    }
}

//Return list bottom-up

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        
        List<Integer> list= new ArrayList<Integer>();
        List<List<Integer>> listList= new ArrayList<List<Integer>>();
        List<List<Integer>> listListBottomUp= new ArrayList<List<Integer>>();
        
        if (root == null) return listList;
        
        Queue<TreeNode> treeQueue = new LinkedList<TreeNode>();
        
        int countCurrentLevel = 1;
        int countNextLevel = 0;
        
        treeQueue.add(root);
        while (!treeQueue.isEmpty()){
            TreeNode node = treeQueue.remove();
            list.add(node.val);
            countCurrentLevel--;
            if (node.left != null){
                treeQueue.add(node.left);
                countNextLevel++;
            }
            if (node.right != null){
                treeQueue.add(node.right);
                countNextLevel++;
            }
            
            if (countCurrentLevel == 0){
                listList.add(list);
                list = new ArrayList<Integer>();
                countCurrentLevel = countNextLevel;
                countNextLevel = 0;
            }
            
        }
        
        for(int i = listList.size() - 1; i >= 0; i--){
            listListBottomUp.add(listList.get(i));
        }
        
        return listListBottomUp;
        
    }
}