Vertical order traversal of Binary Tree using Map

We all must have encountered the vertical Traversal of the Binary Tree problem.
In this version of the problem we will see how we can perform the traversal vertically while keeping in mind that the order should be from left to right(just like increasing x coordinates):

If the x coordinates are same then the node appearing on the upper level should come first.
If the y coordinates as well as x coordinates are same the the node with the smaller value should come first.

Examples:

Input :
             1
          /     \
         2       3
        /  \    /  \
       4    5  6    7
Output : 
[[4], [2], [1, 5, 6], [3], [7]]

Explanation:
Here the nodes with values 5 and 6 respectively have the same x coordinates (horizontal distance from left). 
Same y coordinates (height from the root) but since 5 is smaller than 6 it comes first.

Input :
             3
          /     \
         9       20
                /  \
               15  17 
Output :
[[9], [3, 15], [20], [7]]

A sample example to visualize the vertical traversel better:

A sample example how the vertical traversel works

Naive Approach:

One way can be to perform the level order traversal of the tree and use TreeMap (in Java).
Since it is according to the conditions(related to x and y coordinates) of the traversal of the tree stated above. But it doesn’t take into account the fact that if two nodes have same x and y coordinates. Then it can’t check which node’s value is smaller or greater.

Efficient Approach:

We will use TreeMap in Java since it implements self balancing binary search tree and hence it stores keys in ascending order.
In the map we will store the x coordinates as keys the values will be an ArrayList containing Nodes on the same x coordinate.
This will solve the issue of traversing the tree from left to right due to the TreeMap property stated int the first point
Now since sorting on the basis of x coordinate is done we have to care about now the y coordinate and the node’s values.
The ArrayList stored as values of the map will be sorted on the basis of y coordinate first and then according to the value of the node.

Below is the implementation of the above approach:

import java.util.*;
class Node {
    int data;
    Node right, left;
    Node(int d)
    {
        data = d;
    }
}
class Tree {
    class Pair { // This class contains the node and it's y coordinate
        Node node;
        int y; // y denotes height of the Node
        Pair(Node node, int y)
        {
            this.node = node;
            this.y = y;
        }
    }

    void dfs(Node root, int x, int y, TreeMap<Integer, ArrayList<Pair> > tm)
    {
        if (root == null)
            return;
        if (tm.containsKey(x)) {
            // If that x coordinate already exists then it's array list add the current pair
            tm.get(x).add(new Pair(root, y));
        }
        else {
            ArrayList<Pair> al = new ArrayList<>();
            al.add(new Pair(root, y));
            tm.put(x, al);
        }
        // While moving left we have to decrease the x coordinate.
        dfs(root.left, x - 1, y + 1, tm);

        // While moving right the x coordinate increases.
        dfs(root.right, x + 1, y + 1, tm);
    }
    ArrayList<ArrayList<Integer> > vertical(Node root)
    {
        // Tree Map to store the x coordinate as keys and ArrayList
        // of type Pair which contains the node's reference and y coordinate
        TreeMap<Integer, ArrayList<Pair> > tm = new TreeMap<>();

        // The root is at (0, 0)
        dfs(root, 0, 0, tm);
        ArrayList<ArrayList<Integer> > res = new ArrayList<>();
        for (Map.Entry<Integer, ArrayList<Pair> > m : tm.entrySet()) {

            ArrayList<Pair> temp = m.getValue();
            // using the Comparator Interface in Java
            Collections.sort(temp, new Comparator<Pair>() {
                public int compare(Pair p1, Pair p2)
                {
                    // First sort according to the height
                    int k = Integer.compare(p1.y, p2.y);

                    // If height is equal then sort according to the node value
                    return (k == 0) ? Integer.compare(p1.node.data, p2.node.data) : k;
                }
            });
            ArrayList<Integer> temp1 = new ArrayList<>();

            // Making a temporary list and adding the corresponding Pair's value
            for (Pair i : temp) {
                temp1.add(i.node.data);
            }
            res.add(temp1);
        }
        return res;
    }
}
public class abc {
    public static void main(String[] args)
    {
        Node root = new Node(1);
        root.left = new Node(2);
        root.left.left = new Node(4);
        root.left.right = new Node(6);
        root.right = new Node(3);
        root.right.left = new Node(5);
        root.right.right = new Node(7);
        ArrayList<ArrayList<Integer> > al = new Tree().vertical(root);
        System.out.println(al);
    }
}

Output :

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

The time complexity of the above problem is O(nlogn).

Please write comments below if you find anything incorrect, or you want to share more information about the topic discussed above. A gentle request to share this topic on your social media profile.