[CC150][4.4] Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (i e , if you have a tree with depth D, you’ll have D linked lists)

BST.java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.ListIterator;

public class BST<Key extends Comparable<Key>> {
	private Node root;
	
	private class Node {
		private Key key;
		private Node left, right;
		public Node(Key key) {
			this.key = key;
		}
	}
	public BST(Key[] keys) {
		root = put(root, 0, keys.length - 1, keys);
	}
	
	private Node put(Node x, int low, int high, Key[] keys) {
		if ( low  > high) return null;
		int mid = (low + high) / 2;
		x = new Node(keys[mid]);
		x.left = put(x.left, low, mid - 1, keys);
		x.right = put(x.right, mid + 1, high, keys);
		return x;
	}
	
	public ArrayList<LinkedList<Node>> getAllLvs() {
		ArrayList<LinkedList<Node>> allLvs = new ArrayList<LinkedList<Node>>();
		LinkedList<Node> list = new LinkedList<Node>();
		list.add(root);
		allLvs.add(list);
		int lv = 0;
		while (!isEmpty(allLvs.get(lv))) {
			ListIterator<Node> iter = allLvs.get(lv).listIterator();
			Node curr;
			list = new LinkedList<Node>();
			while (iter.hasNext()) {
				curr = iter.next();
				list.add(curr == null ? null : curr.left);
				list.add(curr == null ? null : curr.right);
			}
			allLvs.add(list);
			lv++;
		}
		allLvs.remove(lv);
		return allLvs;
	}
	
	private boolean isEmpty(LinkedList<Node> list) {
		ListIterator<Node> iter = list.listIterator();
		while (iter.hasNext()) {
			if (iter.next() != null)
				return false;
		}
		return true;
	}
	
	
	public String toString(ArrayList<LinkedList<Node>> allLvs) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < allLvs.size(); i++) {
			for (Node each : allLvs.get(i)) {
				if (each == null)
					sb.append("null" + " ");
				else
					sb.append(each.key.toString() + " ");
			}
			sb.append("\n");	
		}
		return sb.toString();
	}
	
	public static void main(String[] args) {
		Integer[] data = {1,2,3,4,5,6,7,8,9,10,11};
		BST<Integer> test = new BST<Integer>(data);
		System.out.println(test.toString(test.getAllLvs()));
	}
}