Elevate 24x7
😀Starting our Insight
Vertical Path Traversal is said to be one of the hard level problems that is frequently asked among the MAANG companies (Microsoft, Apple, Amazon, Netflix, Google).
Vertical Order Traversal can be very useful for multi-threading and parallel processing of nodes/processes at same vertical level, converting binary tree into doubly linked list, column-wise sum, vertical sum, top view or bottom view in binary tree and printing binary tree columns
Here with this post, our main motive is to dig into a basic insight on understanding and solving this problem.
 |
| example - 1 |
Input: root = [3,9,20,null,null,15,7] Output: [[9],[3,15],[20],[7]]
In the above example, the the input shows a level order traversal of the above tree in an input array of the tree elements.
The output shows the vertical order traversal. Above each node we find coordinates, in which the x-coordinate implies the row and y-coordinate implies a column. The rows are in the order - [0,1,2..], whereas the columns in [....-1,0,1,2..].
Let's look at an another example to analyze the insight...
😁Analyzing our Insight
 |
| example -2 |
Input: root = [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Here is an another example which two node elements 5 and 6 are in the same row and in the same column - (2,0). In the Output, we can make an observation that in the column 0, we have got three elements - [1,5,6], in which the sorting seems to be in increasing order. But it is not always the case. The sorting would be in ascending order, only if the elements belong to the same row. If for instance, 8 would have been the root element instead of 1, then the array should be [8,5,6] in the vertical order traversal for the column 0, and not [5,6,8]. Thus to know more on this, lets dig deeper into the insight...
😄Digging Deeper into our Insight
In order to dig deep and have the basic idea to approach this problem from the above observations, we need to be sure about the method we need to use over here. Since while displaying the vertical order traversal, we need to initially go from column to column, and then keep printing the elements, keeping in mind that elements should be displayed from the down the rows, with the elements in the same row in a sorted fashion.
Which data structure to use here? We may initially think over using array within an array...
But here we also know that the column indexing is on an integer number line, with negative numbers, zero and positive numbers. When the indexing is negative, array can never be used, then? We can use a Map with an integer as the key for the column and a list of row elements as the value.
But there is one thing to be careful about. If we just use a list of row elements in an increasing order as the value, then we may fail some test cases, with the second example as shown above. So thus for the value of the map, we can make use of a TreeMap of integer as the key for the row element and a list of integers for the sorted row elements. TreeMap ensures the sorted order of its value elements for each row.
Hmm, ok lets see the basic algorithm to solve this...
0)We initialize the minimum column and maximum column as zero.
1)We need to build a traversal map with the above features as described.
a)While building we first need to ensure the corner cases as to if the root is null, then we return from execution.
b)If the vertical map does not contain the key column, then we ass the column followed by the value TreeMap.
c)If the column exists, we get the key column, and add the row and its corresponding list of row elements as the value of the TreeMap.
d) If the column as well as the row exists, then we add get both of them and add the list of row elements in the value TreeMap.
e)We then use the two initialized variables for minimum column an maximum column to traverse from one column to another.
f)And while traversing column wise, we use recursion, one for going to the left column, down the row and the other for going to the right column, down the row.
2)After building the vertical traversal map, we then iterate from minimum column towards the maximum column, go to each and sort the row elements only if they belong to the same row and same column. We then assign the result to a list within a list.
3)Then we return the resultant List within a list after the assigning the result.
I guess we are very well done with the excavation. What follows? Lets do the extraction!
Extracting data from our Insight😊
And lo! We have come to the final stage of our process. Lets have a look at the code snippet, that we can derive from the above algorithm:-
here 0),1),2) .. statements are the corresponding code snippets for the steps used in the above algorithm.
0) int minCol = 0, maxCol = 0;
1) public void buildTraversalMap(TreeNode root, int col, int row, Map<Integer, TreeMap<Integer, List<Integer>>> verticalMap) {
1a) if(root == null)
return;
1b)if(!verticalMap.containsKey(col)) {
verticalMap.put(col, new TreeMap<>());
}
1c)if(!verticalMap.get(col).containsKey(row)){
verticalMap.get(col).put(row, new ArrayList<>());
}
1d)verticalMap.get(col).get(row).add(root.val);
1e) minCol = Math.min(minCol, col);
maxCol = Math.max(maxCol, col);
1f) buildTraversalMap(root.left, col-1, row+1, verticalMap);
buildTraversalMap(root.right, col+1, row+1, verticalMap);
}
2) public List<List<Integer>> verticalTraversal(TreeNode root) {
Map<Integer, TreeMap<Integer, List<Integer>>> verticalMap = new TreeMap<>();
buildTraversalMap(root, 0,0,verticalMap);
List<List<Integer>> finalPath = new ArrayList<>();
for(int i=minCol; i<=maxCol; i++){
List<Integer> verticalPath = new ArrayList<>();
for(List<Integer> values : verticalMap.get(i).values()){
Collections.sort(values);
verticalPath.addAll(values);
}
finalPath.add(verticalPath);
}
3) return finalPath;
}
Thank you!!!
Comments
Post a Comment