List at each depth of a binary tree

Problem: Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth (e.g., if you have a tree with depth D, you’ll have D linked lists).

My solution:

public class BinaryNode {

	private BinaryNode left;
	private BinaryNode right;
	private int value;
	...

     /**
	 * Populates the argument mapOfLists with a linked list of elements at each
	 * depth. The key of the map will be the depth (starting with 0).
	 *
	 * To invoke this on an entire binary tree, call providing the root
	 * BinaryNode and a depth of 0.
	 *
	 * @param node BinaryNode to process in the current iteration
	 * @param depth starting with 0
	 * @param mapOfLists see above
	 */
	public static void createMapOfOneListPerDepth(BinaryNode node, int depth,
			Map<Integer, LinkedList<BinaryNode>> mapOfLists) {
		if (node == null) {
			return;
		}
		if (mapOfLists.get(depth) == null) {
			mapOfLists.put(depth, new LinkedList<BinaryNode>());
		}
		mapOfLists.get(depth).add(node);
		depth++;
		createMapOfOneListPerDepth(node.getLeft(), depth, mapOfLists);
		createMapOfOneListPerDepth(node.getRight(), depth, mapOfLists);
		depth--;
		return;
	}

Full code including accompanying JUnit tests can be found at my GitHub.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s