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

Here is Map based java implementation

 public static<T extends Comparable<? super T>> List<List<T>> mapBasedVerticalView(BinaryTreeNode<T> node) {
    Map<Integer, List<BinaryTreeNode<T>>> map = new TreeMap<Integer, List<BinaryTreeNode<T>>>();
    List<List<T>> result = new ArrayList<List<T>>();
    populateHDMap(node, 0 , map);
    populateResult(map, result);
    return result;
}

private static<T extends Comparable<? super T>> void populateHDMap(BinaryTreeNode<T> node, int hd, Map<Integer, List<BinaryTreeNode<T>>> map) {
    if (node == null) {
        return ;
    }
    updateHDNode(node, hd, map);
    populateHDMap(node.getLeft(), hd - 1, map);
    populateHDMap(node.getRight(), hd + 1, map);

}

private static <T extends Comparable<? super T>> void updateHDNode(BinaryTreeNode<T> node, Integer hd, Map<Integer, List<BinaryTreeNode<T>>> map) {
    List<BinaryTreeNode<T>> list = map.get(hd);
    if (list == null) {
        list = new ArrayList<BinaryTreeNode<T>>();
        map.put(hd, list);
    }
    list.add(node);
}

private static<T extends Comparable<? super T>> void populateResult(Map<Integer, List<BinaryTreeNode<T>>> map, List<List<T>> result) {
    for (Map.Entry<Integer, List<BinaryTreeNode<T>>> entry : map.entrySet()) {
        List<T> items = new ArrayList<T>();
        for (BinaryTreeNode<T> bt :entry.getValue()) {
            items.add(bt.getData());
        }
        result.add(items);
    }
}

Here is Unit Test

@Test
public void printMapBasedVerticalViewTest() {
    BinaryTreeNode<Integer> node = BinaryTreeUtil.<Integer>fromInAndPostOrder(new Integer[]{4,2,5,1,6,3,7}, new Integer[]{4,5,2,6,7,3,1});

    List<List<Integer>> rightView = BinaryTreeUtil.<Integer>mapBasedVerticalView(node);

    assertThat(rightView.size(), is(5));
    assertThat(rightView.get(0).toArray(new Integer[0]), equalTo(new Integer[]{4}));
    assertThat(rightView.get(1).toArray(new Integer[0]), equalTo(new Integer[]{2}));
    assertThat(rightView.get(2).toArray(new Integer[0]), equalTo(new Integer[]{1,5,6}));
    assertThat(rightView.get(3).toArray(new Integer[0]), equalTo(new Integer[]{3}));
    assertThat(rightView.get(4).toArray(new Integer[0]), equalTo(new Integer[]{7}));
}

Answer 2

Here is the java implementation (non hashmap based)

public static <T extends Comparable<? super T>> List<List<T>> verticalView(BinaryTreeNode<T> node) {
    List<List<T>> result = new ArrayList<List<T>>();
    MutableInteger min = new MutableInteger(0);
    MutableInteger max = new MutableInteger(0);
    findMinMaxHD(node, min, max, 0);

    printVeritcalVew(node, min.getValue(), max.getValue(), result);

    return result;
}

private static <T extends Comparable<? super T>> void findMinMaxHD(BinaryTreeNode<T> node, MutableInteger min, MutableInteger max, int hd) {
    if (node == null) {
        return;
    }
    min.updateForMin(hd);
    max.updateForMax(hd);
    findMinMaxHD(node.getLeft(), min, max, hd - 1);
    findMinMaxHD(node.getRight(), min, max, hd + 1);
}

private static <T extends Comparable<? super T>> void printVeritcalVew(BinaryTreeNode<T> node, Integer min, Integer max, List<List<T>> result) {
    if (node == null) {
        return ;
    }

    for (int lineNo = min; lineNo <= max; lineNo++) {
        List<T> lineResult = new ArrayList<T>();
        doPrintVerticalView(node, lineNo, 0, lineResult);
        result.add(lineResult);
    }
}

private static <T extends Comparable<? super T>> void doPrintVerticalView(BinaryTreeNode<T> node, int lineNo, int hd, List<T> lineResult) {
    if (node == null) {
        return ;
    }
    if (lineNo == hd) {
        lineResult.add(node.getData());
    }
    doPrintVerticalView(node.getLeft(), lineNo, hd - 1, lineResult);
    doPrintVerticalView(node.getRight(), lineNo, hd + 1, lineResult);

}

Here is the Unit Test case

@Test
public void printVerticalViewTest() {
    BinaryTreeNode<Integer> node = BinaryTreeUtil.<Integer>fromInAndPostOrder(new Integer[]{4,2,5,1,6,3,7}, new Integer[]{4,5,2,6,7,3,1});

    List<List<Integer>> rightView = BinaryTreeUtil.<Integer>verticalView(node);

    assertThat(rightView.size(), is(5));
    assertThat(rightView.get(0).toArray(new Integer[0]), equalTo(new Integer[]{4}));
    assertThat(rightView.get(1).toArray(new Integer[0]), equalTo(new Integer[]{2}));
    assertThat(rightView.get(2).toArray(new Integer[0]), equalTo(new Integer[]{1,5,6}));
    assertThat(rightView.get(3).toArray(new Integer[0]), equalTo(new Integer[]{3}));
    assertThat(rightView.get(4).toArray(new Integer[0]), equalTo(new Integer[]{7}));
}

Here is the Mutable Integer Class

public class MutableInteger {
private Integer value;

public MutableInteger(Integer val) {
    this.value = val;
}

public boolean updateForMax(Integer newValue) {
    if (this.value < newValue) {
        this.value = newValue;
        return true;
    }
    return false;
}

public boolean updateForMin(Integer newValue) {
    if (this.value > newValue) {
        this.value = newValue;
        return true;
    }
    return false;
}

public Integer getValue() {
    return value;
}

public void setValue(Integer value) {
    this.value = value;
}

@Override
public String toString() {
    return String.valueOf(value);
}

Answer 3

public List<ArrayList<TreeNode>> getVerticalView() {
    List<ArrayList<TreeNode>> ans = new ArrayList<ArrayList<TreeNode>>();
    Map<Integer, List<TreeNode>> map = new LinkedHashMap<Integer, List<TreeNode>>(); // Linked
                                                                                        // hash
                                                                                        // map,
                                                                                        // entry
                                                                                        // set
                                                                                        // will
                                                                                        // run
                                                                                        // in
                                                                                        // insertion
                                                                                        // order
    getVerticalpart(root, map, 0);
    int index = 0;
    for (Map.Entry<Integer, List<TreeNode>> entry : map.entrySet()) {
        ans.add(index, (ArrayList<TreeNode>) entry.getValue());
        index++;
    }
    return ans;
}

private void getVerticalpart(TreeNode root, Map<Integer, List<TreeNode>> map, int i) {
    if (root == null)
        return;
    /**
     * Idea is to to inorder traversal of tree. Just put the node in the map
     * according to value of i
     */
    getVerticalpart(root.left, map, i - 1);

    if (!map.containsKey(i)) {
        map.put(i, new ArrayList<>());
    }
    List<TreeNode> l = map.get(i);
    l.add(root);

    getVerticalpart(root.right, map, i + 1);
}

Answer 4

Doubly-Link List approach: Think of each vertical list as a node in a doubly linked list: Node1 <-> Node2 <-> Node3 <->Node4.....

Node1: 8 Node2: 4 Node3: 2,9 Node4: 1,5,6 ...

The idea is: when you walk to left child/parent, you go to the left node in linked list, store the tree node into current linked list node; when you walk to right child/parent, you go the right node in linked list, store into node like above.

The left most node would store the left most vertical list, Node1 in this case, you can print this linked list from left to right to get final result.

Answer 5

Check the horizontal distance from root to all nodes, if two nodes have the same horizontal distance, then they are on same vertical line. Store this horizontal distance into hash map.

C++ codes

struct Node
{
    int val;
    Node* left, *right;
};

void getHD(Node* root, int hd, map<int, vector<int>> &hmap)
{
    if (root == nullptr)
        return;

    // store current node in hash map
    hmap[hd].push_back(root->val);

    getHD(root->left, hd-1, hmap);

    getHD(root->right, hd+1, hmap);
}

void printHD(Node* root)
{
    map<int, vector<int>> hmap;
    getHD(root, 0, hmap);

    for (auto it = std::begin(hmap), en = std::end(hmap); it != en; ++it)
    {
        for (auto v : it->second)
            cout << v << " ";
        cout << endl;
    }
}

Answer 6

This require 3 passes full traversal if you want to really print them, instead of only storing them.

If we use map instead of array, and also we just need to store nodes in lists by vertical lines, not printing, then 1 pass full traversal is enough.

---

The idea below assumes we can't use map, just use array.

1. Every node has a virtual pos, left child will have pos-1, and right child will have pos+1

2. Traversal the whole tree (whatever order), record the leftmost pos *min_pos* and right most pos *max_pos*. (1st pass)

3. create an array length is max_pos-min_pos+1, each slot is an empty list

4. Traversal the whole tree again, with the array, the min_pos and keep tracking the pos. When visiting a node, we get its pos, we add the node to the array via the index pos - min_pos. (2nd pass)

5. print all lists in the array (3rd pass)

---

Here are the code in OCaml, without the last print part.

type 'a btree = Empty | Node of 'a btree * 'a * 'a btree

let min3 x y z = min (min x y) z
let max3 x y z = max (max x y) z

let range btree = 
  let rec get_range (min_pos, max_pos) pos = function
  | Empty -> min_pos, max_pos
  | Node (l, _, r) ->
    let min1, max1 = get_range (min_pos,max_pos) (pos-1) l in
    let min2, max2 = get_range (min_pos,max_pos) (pos+1) r in
    min3 min1 min2 pos, max3 max1 max2 pos
  in 
  get_range (0, 0) 0 btree

let by_vertical (min_pos, max_pos) btree = 
  let a = Array.make (max_pos-min_pos+1) [] in
  let rec traversal pos = function
    | Empty -> ()
    | Node (l, k, r) -> (
      a.(pos-min_pos) <- k::a.(pos-min_pos);
      traversal (pos-1) l;
      traversal (pos+1) r;
    )
  in 
  traversal 0 btree;
  a;;

let in_vertical btree = by_vertical (range btree) btree

Answer 7

This task can be achieved by simple structure known as zipper. This structure serves well for keeping state during traveling through list. It is technically structure which splits (single) linked list to two parts. First is part of list left (or in front) of current place stored in reverse order and second part is members left. Imagine it as structure like this

struct {
  list *revleft;
  list *right;
};

Or in some functional language with lists as single linked list, for example Erlang

{Left, Right}

Each member of those lists will be list containing one vertical line.

Then we have to define operations zip_left and zip_right. Each of this operation will move one element from one side of zipper to other side. This operation have to also make empty list if there is not any element to remove. For example in Erlang:

zip_left({[], R})    -> {[], [[]|R]};  % make empty list and add to right
zip_left({[H|T], R}) -> {T,  [H |R]}.  % move head to right

zip_right({L, []})    -> {[[]|L], []}; % make empty list and add to left
zip_right({L, [H|T]}) -> {[H |L], T}.  % move head to left

[H|T] is operation of removing head of list or adding new head to list depending which side of -> it is. At left side it removes, at right side it adds.

Then we need define operation zip_add which adds tree node value to corresponding vertical line. Just for convention assume current value is head of right side of zipper. We have to cope with empty list.

zip_add(V, {L, [   ]}) -> {L, [[V]    ]}); % add value to empty list
zip_add(V, {L, [H|R]}) -> {L, [[V|H]|R]}.  % add value to right head

And now we have to simply send zipper around the tree. When we will go to the right we will move zip to the right and then when returns form subtree back to left. When we will go to the left, we will move zip to left and then to right. It doesn't matter in which order. It affect only order of values in each vertical line.

-record(node, {
        value,
        left = nil,
        right = nil
        }).

zip_new() -> {[], []}. % new empty zipper

get_verical_lines(Root) ->
    {L, R} = get_verical_lines(Root, zip_new()),
    tl(lists:reverse(L, R)). % concatenate zipper and cut off surplus empty list

get_verical_lines(nil, Zip) -> Zip;
get_verical_lines(#node{value = V, left = L, right = R}, Zip) ->
    Zip1 = zip_right(get_verical_lines(L, zip_left(Zip))),
    Zip2 = zip_left(get_verical_lines(R, zip_right(Zip1))),
    zip_add(V, Zip2).

And that is all. All operations zip_left, zip_right and zip_add are O(1) operations. In each node we perform them fixed number of times (zip_leftx2, zip_rightx2, zip_addx1) so it is nice O(N) with only simple single linked list structure. Implementation in any language is pretty straightforward except it will be less verbose.

First tree form question

> io:write(vertical_tree:get_verical_lines({node, 1, {node, 2, {node, 4, nil, nil}, {node, 5, nil, nil}}, {node, 3, {node, 6, nil, nil}, {node, 7, nil, nil}}})).
[[4],[2],[1,6,5],[3],[7]]ok

Second tree

> io:write(vertical_tree:get_verical_lines({node, 1, {node, 2, {node, 4, {node, 8, nil, nil}, {node, 9, nil, nil}}, {node, 5, nil, nil}}, {node, 3, {node, 6, nil ,nil},{node, 7, {node, 10, nil, nil}, {node, 11, nil, nil}}}})).
[[8],[4],[2,9],[1,6,5],[3,10],[7],[11]]ok

There is full module code including tree pretty printer.

> io:put_chars(vertical_tree:draw({node, 1, {node, 2, {node, 4, nil, nil}, {node, 5, nil, nil}}, {node, 3, {node, 6, nil, nil}, {node, 7, nil, nil}}})). 
   1 
  / \
 2   3 
/ \ / \
4 5 6 7 
ok
> io:put_chars(vertical_tree:draw({node, 1, {node, 2, {node, 4, {node, 8, nil, nil}, {node, 9, nil, nil}}, {node, 5, nil, nil}}, {node, 3, {node, 6, nil ,nil},{node, 7, {node, 10, nil, nil}, {node, 11, nil, nil}}}})).   
     1 
    / \
   2   3 
  / \ / \
 4  5 6  7 
/ \     / \
8 9    10 11 
ok

BTW There is much more types of zippers than for working with single linked lists. For example there can be made zipper for traversing trees which allows traverse list without recursion or using only tail recursive functions.

Answer 8

I doubt the double-linked-list solution is much faster than the Map solution, but I think you could do it this way:

when traversing the tree each time you go left, you pass the left-node of the double-linked list + the Horizontal distance of that node (i.e the crt hd-1). Something similar with the go-right case.

Answer 9

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.