Bottom Up (or Reverse) Level Order Traversal of a BST/Binary-Tree [O(N) where N is the number of nodes]

levelOrderBottomUpBST.java

// Problem link: https://practice.geeksforgeeks.org/problems/reverse-level-order-traversal/1
import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.Arrays;
import java.util.LinkedList;

public class BST {
    
    class Node {
        public int key, depth;
        Node left, right;
        Node(int key, int depth) {
            this.key = key;
            this.depth = depth;
            this.left = null;
            this.right = null;
        }
    }
    
    public ArrayList<ArrayList<Integer>> result;
    public Node ROOT;
    BST() { 
        this.ROOT = null; 
        this.result = new ArrayList<ArrayList<Integer>>();
    }
    
    void insertRec(Node root, Node node) {
        final int key = node.key;
        ++node.depth;
        if(key < root.key) {
            if(root.left == null) root.left = node;
            else insertRec(root.left, node);
        } else {
            if(root.right == null) root.right = node;
            else insertRec(root.right, node);
        }
    }
    
    void insert(final int key) {
        Node node = new Node(key, 0);
        if(this.ROOT == null) this.ROOT = node;
        else insertRec(ROOT, node);
    }
    
    void level_order(Node root) {
        Queue<Node> Q = new LinkedList<Node>();
        boolean[] count = new boolean[1001];
        Arrays.fill(count, false);
        Q.add(root);
        while(!Q.isEmpty()) {
            Node node = Q.remove();
            if(!count[node.depth]) {
                count[node.depth] = true;
                ArrayList<Integer> temp = new ArrayList<Integer>();
                temp.add(node.key);
                this.result.add(temp);
            } else this.result.get(node.depth).add(node.key);
            
            if(node.left == null && node.right == null) continue;
            else if(node.left == null) Q.add(node.right);
            else if(node.right == null) Q.add(node.left);
            else {
                Q.add(node.left);
                Q.add(node.right);
            }
        }
        
        // Printing the elements inside the result ArrayList
        for(int i = this.result.size()-1; i >= 0; --i) {
            for(int j = 0; j < this.result.get(i).size(); ++j)
                System.out.print(this.result.get(i).get(j) + " ");
            System.out.println();
        }
    }
    
    
    // TEST FUNCTION
    void inorder(Node root) {
        if(root != null) {
            inorder(root.left);
            System.out.println(root.key + " " + root.depth);
            inorder(root.right);
        }
    }
    
    public static void main(String[] args) throws Exception {
        Scanner scan = new Scanner(System.in);
        int t = scan.nextInt();
        while(t-- > 0) {
            BST tree = new BST();
            int n = scan.nextInt();
            for(int i = 0; i < n; ++i) tree.insert(scan.nextInt());
            // tree.inorder(tree.ROOT);
            tree.level_order(tree.ROOT);
            if(t != 0) System.out.println();
        }
    }
}