Given the following tree, how would you print out the nodes in the following order: 0, 1, 2, 3, 4, 5? (interview question)
0
/ \
1 2
/ \ /
3 4 5

**Breadth-first Traversal:**

The problem can be solved with breadth-first (level-order) traversal, using an intermediate queue and iteration:
public void breadthFirstIterative(Node root){
Queue<Node> q = new LinkedList<Node>();
q.add(root);
while(!q.isEmpty()){
Node node = q.poll();
System.out.println(node.data);
if(node.left != null){
q.add(node.left);
}
if(node.right != null){
q.add(node.right);
}
}
}

You can also solve it using recursion, but this is not efficient and not recommended.
public void breadthFirstRecursive(Node root) {
Map<Integer, List<Node>> map =
new TreeMap<Integer, List<Node>>();
breadthFirst2(root, map, 0);
for (int i : map.keySet()) {
List<Node> nodes = map.get(i);
for(Node node : nodes){
System.out.println(node);
}
}
}
private void breadthFirst2(Node node,
Map<Integer, List<Node>> map,
int level) {
List<Node> nodes = map.get(level);
if (nodes == null) {
nodes = new ArrayList<Node>();
map.put(level, nodes);
}
nodes.add(node);
if (node.left != null) {
breadthFirst2(node.left, map, level + 1);
}
if (node.right != null) {
breadthFirst2(node.right, map, level + 1);
}
}

**Depth-first Traversal:**

Just for completeness, I will also show you the algorithm for depth-first traversal, which will not print out 0, 1, 2, 3, 4, 5 but will print out 0, 1, 3, 4, 2, 5. Here is the algorithm using a stack and iteration:
public void depthFirstIterative(Node root) {
Stack<Node> s = new Stack<Node>();
s.push(root);
while (!s.isEmpty()) {
Node node = s.pop();
System.out.println(node);
if (node.right != null) {
s.push(node.right);
}
if (node.left != null) {
s.push(node.left);
}
}
}

You can also solve it using recursion:
public void depthFirstRecursive(Node root) {
System.out.println(root);
if (root.left != null) {
depthFirstRecursive(root.left);
}
if (root.right != null) {
depthFirstRecursive(root.right);
}
}