Vertical Order Traversal of a Binary Tree

If we are given a binary tree and we need to perform a vertical order traversal, that means we will be processing the nodes of the binary tree from left to right. Suppose we have a tree such as the one given below.

If we traverse the tree in vertical order and print the nodes then the output will be:

4,
2,
1, 5, 6,
3,
7,

In order to traverse vertically we will require some method to reduce the complexity of traversing the binary tree. We will do this by assigning a horizontal distance to each node.

Horizontal Distance (HD): is the distance of a node from the root node. The HD of the root node is zero. Any node that falls in the vertical line after the root node line will be positive, and any node that falls in the vertical line to the left of the root node will be negative.
Take the example of the tree above. The horizontal distance of nodes will be:

HD (-2)–> 4
HD (-1)–> 2
HD (0)–> 1, 5, 6
HD (+1)–> 3
HD (+2)–> 7

Algorithm

We need to find and store the HD for each node.
HD —> Horizontal Distance

Declaration:

queue --> q // to insert nodes
queue --> indices // to insert HD and keep track of HD for each node
mp --> HashMap // key --HD , Values --> ArrayList (will contain nodes for particular HD)
minHD =0 , maxHD=0 // so that we can move from minHD to maxHD

Execution:

Step1: Loop (until q is empty)
if queue is not empty then go to step 2
else go to step ------

Step2: Loop (find size of q )
If reached end of loop got to step 1
else go to step 3

Step3: node = q.poll() // get the current Node
index= indices.poll() // get the index for current node
put the index in Map // if not present
add the Node into value of Map(ArrayList) for respective index

Step4: Check for left subtree
if the left subtree for current node is not null then
insert into q(node.left)
insert the index-1 for node.left
calculate minHD = min(minHD, index-1)
else go to step 5

Step5: Check for right subtree
if the left subtree for current node is not null then
insert into q(node.right)
insert the index+1 for node.right
calculate maxHD = max(maxHD, index+1)
else go to step 2

Step6: Traverse the map from minHD to maxHD (Map Keys) and print all nodes for respective HD.

Java Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class BinaryTree {
  static ArrayList < Integer > verticalOrder(Node root) {
    //final list which will be returned  
    ArrayList < Integer > res = new ArrayList < > ();
    if (root == null) return res;

    Queue < Node > q = new LinkedList < > ();
    q.offer(root);
    //map to track nodes for each HD
    Map < Integer, List < Integer >> mp = new HashMap < > ();
    //index of each nodes stored in q(queues)
    Queue < Integer > indices = new LinkedList < > ();
    indices.offer(0);
    int minIndex = 0, maxIndex = 0;

    while (!q.isEmpty()) {
      int size = q.size();
      for (int i = 0; i < size; i++) {
        Node node = q.poll();
        int index = indices.poll();

        mp.putIfAbsent(index, new ArrayList < > ());
        mp.get(index)
          .add(node.data);

        if (node.left != null) {
          q.offer(node.left);
          indices.offer(index - 1);
          minIndex = Math.min(minIndex, index - 1);
        }

        if (node.right != null) {
          q.offer(node.right);
          indices.offer(index + 1);
          maxIndex = Math.max(maxIndex, index + 1);
        }
        /*
        [0,2,1,3,null,null,null,4,5,null,7,6,null,10,8,11,9]
        [0,5,1,9,null,2,null,null,null,null,3,4,8,6,null,null,null,7]
        */
      }

    }

    // traversing from minHD to MaxHd and inserting into final  
    //ArrayList
    for (int i = minIndex; i <= maxIndex; i++) { //Collections.sort(mp.get(i));
      int size = mp.get(i)
        .size();
      for (int ii = 0; ii < size; ii++)
        res.add(mp.get(i)
          .get(ii));
    }
    //final list containing number of nodes traversed in Vertical Order
    return res;
  }
}