Create linked lists of all the nodes at each depth for a BST

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)

My initial thoughts:
We just do a level-order traversal throughout the tree. For each level, create a linked list containing all the nodes at that depth. Then extract all of the children for each node to create the next linked list at deeper level.

My initial codes:

	public static List<LinkedList<BinaryTreeNode>> createLinkedLists(
			BinaryTreeNode root) {
		List<LinkedList<BinaryTreeNode>> lists = new ArrayList<LinkedList<BinaryTreeNode>>();
		LinkedList<BinaryTreeNode> level0 = new LinkedList<BinaryTreeNode>();
		level0.add(root);
		lists.add(level0);
		int index = 0;

		while (true) {
			LinkedList<BinaryTreeNode> leveli = new LinkedList<BinaryTreeNode>();
			LinkedList<BinaryTreeNode> upperLevel = lists.get(index);
			for (int i = 0; i < upperLevel.size(); ++i) {
				BinaryTreeNode parent = upperLevel.get(i);
					leveli.add(parent.getLeft());
					leveli.add(parent.getRight());
			}
			if (!leveli.isEmpty()) {
				lists.add(leveli);
				index++;
			} else {
				break;
			}
		}

		return lists;
	}

Comments after running:

NullPointerException in highlighted line 14 and 15. Need to check whether left or right exists before putting into the linked-list. Correction:
				if (parent.getLeft() != null)
					leveli.add(parent.getLeft());
				if (parent.getRight() != null)
					leveli.add(parent.getRight());

Solution:

The solution is identical to my codes:
	public static ArrayList<LinkedList<BinaryTreeNode>> findLevelLinkList(
			BinaryTreeNode root) {
		int level = 0;
		ArrayList<LinkedList<BinaryTreeNode>> result = new ArrayList<LinkedList<BinaryTreeNode>>();
		LinkedList<BinaryTreeNode> list = new LinkedList<BinaryTreeNode>();
		list.add(root);
		result.add(level, list);
		while (true) {
			list = new LinkedList<BinaryTreeNode>();
			for (int i = 0; i < result.get(level).size(); i++) {
				BinaryTreeNode n = result.get(level).get(i);
				if (n != null) {
					if (n.getLeft() != null)
						list.add(n.getLeft());
					if (n.getRight() != null)
						list.add(n.getRight());
				}
			}
			if (list.size() > 0) {
				result.add(level + 1, list);
			} else {
				break;
			}
			level++;
		}
		return result;
	}

					

			

				Advertisements