Tree Traversal

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);
    }
}