Printing a binary tree vertically [duplicate]

Question

I want to print a binary tree vertically. I know a solution using hashmap. But, I read at many places that it can be done by using a doubly linked list. However, I can not make out how to do so. I could not find any understandable material on the net as well. Can somebody please help me with the doubly linked list method?

Example:

        5
    4       3
  6   7   8   9

This gives

6
4
5 7 8
3
9

i.e. it is like a level order traversal in vertical order.

Solution using hash map: Assume that the root is indexed 0, then the left ones will be -1, -2, etc. and right ones will be +1, +2, etc. So, we can build a hash keyed on column number and have a list of all the roots that have that particular column number as value. Then we can simply print the entries in hash.

See this link, read the comment on round 1, technical question 1.

I found the same kind of comment written at many other places as well.

Answer 1

What the interviewer probably meant is to pass a linked list down the tree and give each node a pointer to the list element that represents its column.

Just imagine the linked list to be infinite in both directions, you can easily extend it whenever you hit an end. Every item of the list is in turn a list of nodes:

function traverse(tree_node, list_node):
    if tree_node is NIL:
        return
    list_node.add(tree_node)
    traverse(tree_node.left, list_node.prev)
    traverse(tree_node.right, list_node.next)