Leetcode: Vertical Order Traversal of a Binary Tree

 

This question is asked a lot of Facebook and Bloomberg. 

Given the root of a binary tee, calculate the vertical order traversal of the binary tree. For each node at position (x, y) its left and right children will be at positions (x - 1, y - 1) and (x + 1, y + 1) respectively. 

The vertical order traversal of a binary tree is a list of non-empty reports for each unique x-coordinate from left to right. Each report is a list of all nodes at a given x-coordinate. It should be sorted from the highest y-coordinate to the lowest. Return the vertical order traversal of the binary tree. 

Here are examples: 

Example 1:

Input: root = [3,9,20,null,null,15,7]

Output: [[9],[3,15],[20],[7]]

Explanation: Without loss of generality, we can assume the root node is at position (0, 0):

The node with value 9 occurs at position (-1, -1).

The nodes with values 3 and 15 occur at positions (0, 0) and (0, -2).

The node with value 20 occurs at position (1, -1).

The node with value 7 occurs at position (2, -2).

Example 2:

Input: root = [1,2,3,4,5,6,7]

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

Explanation: The node with value 5 and the node with value 6 have the same position according to the given scheme.

However, in the report [1,5,6], the node with value 5 comes first since 5 is smaller than 6.

When you are given a tree, the first step is that every vertical line can be assumed to have a number. 

When we make the left or right all, we go to vertical line numbers and push the key numbers in and push these numbers. We perform dfs and backtrack to certain nodes, saying that we can do BFS and DFS, and pushed after certain arraylist elements. I will write both the Java and Javascript solutions here, utilizing a Treemap. Here's the iteration: 

Here is a Java TreeMap Solution: 

First, we want to create a depth-first-search solution. 

Then, after that, I basically invoke the dfs with the x and y values and add these values to the corresponding linked list. So, this is basically this is a binary search tree. .offer() inserts a specific element in the priority queue without violating capacity constraints. It goes through all the nodes and discard any null nodes, which means that it visits all the elements once ideally, making it a DFS problem.

So the X changes, and the Y values are basically put into a priority node. 

This is a tree map after putting 1, 5, 3, 2, 4, in order: 

class Solution {

    public List<<List<Integer>> verticalTraversal(Treenode root) {

        //List of TreeMaps with More TreeMaps Containing Priority Queues. 

        TreeMap<Integer, TreeMap<Integer, PriorityQueue<Integer>>> map = new TreeMap<>();

        //Traverse through the TreeMap and Mark all of the Numbers. 

        dfs(root, 0, 0, map);

        //initialize list to return.

        List<List<Integer>> list = new ArrayList<>();

        //iterate through all the treemaps in the treemap.  Go over all the x values

        for(TreeMap<Integer, PriorityQueue<Integer>> ys : map.values()) {

            //each map represents a level. add this level to the arrayList.

            list.add(new ArrayList<>());

            for(PriorityQueue<Integer> nodes: ys.values()) {

                //add to the end of the list the values inside of the priority queue. 

                while(!nodes.isEmpty()) {

                    list.get(list.size() - 1).add(nodes.poll());

                }

            }

        }

        //return this corresponding list. 

        return list;

    }

    private void dfs(Treenode root, int x, int y, TreeMap<Integer, TreeMap<Integer, PriorityQueue<Integer>>> map) {

        if(root == null) return;

        //put x in the map if the map does not contain the key x in a tree 

        if(!map.containsKey(x)) map.put(x, new TreeMap<>());

        //if map contains (x,y) put a new priority queue here. 

        if(!map.get(x).containsKey(y)) map.get(x).put(y, new PriorityQueue<>());

        //given that x and y are the same, offer the value as in the priority queue. 

        map.get(x).get(y).offer(root.val);

        //recursively call methods. 

        dfs(root.left, x - 1, y + 1, map);

        dfs(root.right, x + 1, y + 1, map);

    }

}