CC_4_4

BinaryTreeToLinkedList.java

// Cracking the Coding Interview
// 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).
import java.util.LinkedList;
import java.util.List;
import java.util.Arrays;

class Node {
	public int val;
	public Node left;
	public Node right;
	Node(int v) {
		val = v;
		left = null;
		right = null;
	}
}

class BinaryTreeToLinkedList {
	public static List<List<Integer>> toLinkedList(Node root) {
		LinkedList<Node> q = new LinkedList<Node>();
		Node layerEnd = root;
		q.push(root);
		List<List<Integer>> result = new LinkedList<List<Integer>>();
		List<Integer> curLayer = new LinkedList<Integer>();

		while(!q.isEmpty()) {
			Node cur = q.poll();
			curLayer.add(cur.val);
			if (cur.left != null) {
				q.add(cur.left);
			}
			if (cur.right != null) {
				q.add(cur.right);
			}
			if (layerEnd == cur) {
				// end of a layer
				result.add(curLayer);
				curLayer = new LinkedList<Integer>();
				layerEnd = q.peekLast();
			}
		}
		return result;
	}
	private static boolean areEqual(Object a, Object b) {
		if (a instanceof List) {
			if (!(b instanceof List)) return false;
			if (((List)a).size() != ((List)b).size()) return false;
			int len = ((List)a).size();
			for(int i = 0; i < len; i++) {
				if (!areEqual(((List)a).get(i), ((List)b).get(i))) {
					return false;
				}
			}
			return true;
		} else {
			return a.equals(b);
		}
	}
	public static void main(String[] args) {
		Node root = new Node(0);
		List<List<Integer>> expected = new LinkedList<List<Integer>>();
		expected.add(Arrays.asList(0));
		assert expected.equals(toLinkedList(root));
		root.right = new Node(2);
		expected.add(Arrays.asList(2));
		assert expected.equals(toLinkedList(root));
		root.left = new Node(1);
		root.left.right = new Node(3);
		root.right.left = new Node(4);
		expected.remove(1);
		expected.add(1, Arrays.asList(1, 2));
		expected.add(Arrays.asList(3, 4));
		assert expected.equals(toLinkedList(root));

		System.out.println("Tests Passed");
	}
}