Printing a Binary Tree top-down (column wise)

We have a binary tree, suppose like this:

8
     /   \
    6     10
   / \   /  \
  4   7 9    12
 / \
3   5

We have to print this binary tree in top-down manner - column wise. Note that, 8, 7 & 9 would be considered in same column. So the required output should be:

3
4
6 5
8 7 9
10
12

Currently I've implemented this problem using two maps, and one queue. Here's the method traversal(Node node), which is invoked first time, passing the root node:

public void traverse(Node node) {

    Queue> queue = new LinkedList<>();

    Map>> columnMap = new TreeMap<>();
    Map, Integer> map = new HashMap<>();

    queue.add(node);

    while (!queue.isEmpty()) {

        Node temp = queue.poll();

        if (map.isEmpty()) {
            map.put(temp, 0);
            columnMap.put(0, new ArrayList>(Arrays.asList(temp)));
        }

        int column = map.get(temp);

        if (temp.left() != null) {
            queue.add(temp.left());

            if (columnMap.containsKey(column - 1)) {
                columnMap.get(column - 1).add(temp.left());
            } else {
                columnMap.put(column - 1, new ArrayList>(Arrays.asList(temp.left())));
            }

            map.put(temp.left(), column - 1);
        }

        if (temp.right() != null) {
            queue.add(temp.right());

            if (columnMap.containsKey(column + 1)) {
                columnMap.get(column + 1).add(temp.right());
            } else {
                columnMap.put(column + 1, new ArrayList>(Arrays.asList(temp.right())));
            }

            map.put(temp.right(), column + 1);
        }
    }

    for (Entry>> entry: columnMap.entrySet()) {
        System.out.println("Column - " + entry.getKey() + " : " + entry.getValue());
    }
}

The idea is, starting from root node as column number 0, the left node will have column number -1, and the right node will have column number 1. Then the right node of the left node will again have column numb

Using recursion in this instance helps a lot to reduce code duplication. Particularly, in this case, you have different code blocks depending on whether left() or right() are null.

Using recursion you only need one null check, and this removes a big chunk of code.

The queue is only needed for recursion as well, and, it's purpose was hard to figure out... you should have documented it more carefully...

The map variable is also a variable which has a poorly documented purpose... it's hard to tell what variables are on that, and why.

All in all, your suspicions are right that there's a better way to do this.....

Algorithmically it strikes me that a single Map> is probably the right structure, and that recursion is a better solution.... consider a recursive function:

recurseTraverse(final Node node, final Map>> columnmap, final int column) {
    if (node == null) {
        return;
    }
    List> list = columnmap.get(column);
    if (list == null) {
        list = new ArrayList>();
        columnmap.put(column, list);
    }
    list.add(node);
    recurse(node.left(), columnmap, column - 1);
    recurse(node.right(), columnmap, column + 1);

}

Then calling that with a TreeMap>> you should be able to get an improved version of your result.

public void traverse(Node root) {
    TreeMap>> columnMap = new TreeMap<>();

    recurseTraverse(root, columnMap, 0);

    for (Entry>> entry: columnMap.entrySet()) {
        System.out.println("Column - " + entry.getKey() + " : " + entry.getValue());
    }
}

Update: It has been pointed out by Fihop that this answer produces the incorrect results. While it correctly puts each node in to the correct column, it adds them in a depth-first order:


The accepted solution actually does not work. For example:

1
   / \
  2   3
   \
    4
     \
      5

it gives:

2
1 4
5 3 => should be 3 5???

The right solution to this problem is to perform a breadth first traversal (traversing each row of the tree at a time), which requires a queue, and recursion is no longer the best, or even a viable, solution.

In re-working this answer, I have also actually run the code (rather than just typing it in to an answer), and I have almost 2 more years of experience on this. So, there are some other things to point out.

First up, this code can now use Java 8, and the computeIfAbsent() Map method.

Next, using static methods that are also generic methods makes the dependence on Node become the generic Node. I have still worked the example using Integers, and I have invented what I believe the Node class should be. It's not exactly the way I would write it because the method names left() and right() would probably be named differently. I have also created a rudimentary toString.

Finally, to work the traversal a helper container-class ColumnFind was created to link a node to a column, and allow the temporary storage of the column for when the next level of the tree is traversed.

It pains me that the traversal and the println calls are in the same method, I feel they should be separate, but to keep the code consistent with my earlier answer, I will leave it like that. A Java 8 function passed in to the traversal would be a better solution....

So, here's the traversal code (and it is working in ideone here: http://ideone.com/p8RWmE ).

public static final  void traverse(Node root) {

    final TreeMap>> columnMap = new TreeMap<>();
    final Queue> queue = new LinkedList<>();

    queueChild(0, root, queue);

    while (!queue.isEmpty()) {
        ColumnFind cf = queue.remove();
        int column = cf.column;
        Node node = cf.node;
        columnMap.computeIfAbsent(column, c -> new ArrayList<>()).add(node);
        queueChild(column - 1, node.left(), queue);
        queueChild(column + 1, node.right(), queue);
    }

    for (Entry>> entry: columnMap.entrySet()) {
        System.out.println("Column - " + entry.getKey() + " : " + entry.getValue());
    }
}

private static final  void queueChild(int column, Node node, 
                 Queue> queue) {
    if (node == null) {
        return;
    }
    queue.add(new ColumnFind<>(column, node));
}

StackExchange Code Review Q#36799, answer score: 6