algorithm - Print a Tree Vertically

Question

To understand what's same vertical line, we need to define horizontal distances first. If two nodes have the same Horizontal Distance (HD), then they are on same vertical line. The idea of HD is simple. HD for root is 0, a right edge (edge connecting to right subtree) is considered as +1 horizontal distance and a left edge is considered as -1 horizontal distance. For example, in the below tree, HD for Node 4 is at -2, HD for Node 2 is -1, HD for 5 and 6 is 0 and HD for node 7 is +2.

Examples:

      1
    /   

   2     3

  /    / 
  4  5  6  7

The tree has 5 vertical lines

Vertical-Line-1 has only one node 4

Vertical-Line-2: has only one node 2

Vertical-Line-3: has three nodes: 1,5,6

Vertical-Line-4: has only one node 3

Vertical-Line-5: has only one node 7

Now for the tree

        1            
      /    
    2        3       
   /       /  
  4   5    6    7    
 /            / 
8   9        10   11

For the above tree , we should get the output each vertical level from top to bottom, and left to right horixontally

8

4

2 9

1 5 6 or 1 6 5 ( since 6 and 5 are at same vertical level, and same HD, order doesn't matter in them)

3 10

7

11

One way to do it is by simply creating a multimap of HD's , and do a level order traversal, and push the values into corresponding HD index .Doing this in level order way will guarantee that we visit from top to bottom vertically .Then print the nodes form lowest HD to highest HD, fulfilling us left to right constraint.

I've read somewhere that we can do it in a better way using Doubly-Link List approach or something similar.Any help people ?

Answer 1

You're going to have to visit each node once to get its value - so there's no alternative but to make a full traversal, as you've said. It's trivial to keep track of the current node's Horizontal Distance as you traverse.

You can't know the first value to print until you've traversed the whole tree, so you're going to have to collect all the values into a data structure before printing anything. So the only choice is what data structure to use.

What structures are available to you depends on your language.

I would use your language's equivalent of Java Map<HorizontalDistance,List<Node>>.

I don't see any special requirements for the Map. The List needs to be cheap to add to. If it's a linked list, it should maintain a pointer to its tail, at least. There can't be many mainstream list implementations that don't meet this requirement. The standard Java LinkedList does.

So, you're traversing the tree in order, calling this for each node:

 private void addNode(Map<HorizontalDistance,List<Node>> data, 
                      HorizontalDistance hd, 
                      Node node)
 {
       List<Node> list = data.get(hd); // this is cheap
       list.add(node); // this is cheap too
 }

... then printing it out by iterating through the map keys, printing each list.

---

You could, I suppose, replace the Map with an array/list, mapping your positive HDs to even indices and your negatives to odd ones.

int index = hd < 0 ? ( -2 * hd - 1 ) : 2 * hd;

Depending on the map implementation - and the array implementation - and in some languages, whether you know enough to size the array in advance - this might be faster and more memory-efficient.