Problem
The problem involves taking a binary tree and performing a vertical order traversal. Vertical order traversals have real world applications such as rendering user interfaces,GIS systems and database indexing.It is listed below.
Given the root of a binary tree, calculate the vertical order traversal of the binary tree.
For each node at position (row, col), its left and right children will be at positions (row + 1, col - 1) and (row + 1, col + 1) respectively. The root of the tree is at (0, 0).
The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values.
Return the vertical order traversal of the binary tree.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation:
Column -1: Only node 9 is in this column.
Column 0: Nodes 3 and 15 are in this column in that order from top to bottom.
Column 1: Only node 20 is in this column.
Column 2: Only node 7 is in this column.
Example 2:
Input: root = [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation:
Column -2: Only node 4 is in this column.
Column -1: Only node 2 is in this column.
Column 0: Nodes 1, 5, and 6 are in this column.
1 is at the top, so it comes first.
5 and 6 are at the same position (2, 0), so we order them by their value, 5 before 6.
Column 1: Only node 3 is in this column.
Column 2: Only node 7 is in this column.
Example 3:
Input: root = [1,2,3,4,6,5,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation:
This case is the exact same as example 2, but with nodes 5 and 6 swapped.
Note that the solution remains the same since 5 and 6 are in the same location and should be ordered by their values.
Constraints:
The number of nodes in the tree is in the range [1, 1000].
0 <= Node.val <= 1000
My Approach
I decided to make use of a recursive method which performs a depth first search on the tree and returns a hashmap. This hashmap returns a list of all the treenodes along with an integer arraylist of their row and column values. This method is called in the main method by the verticalTraversal method to produce a hashmap tree. The verticalTraversal method traverses the hashmap, forming a list of the distinct columns columns, a hashmap of each column and its list of rows columnsAndRows and a hashmap of each row:column pair and its treenode treeNodesByRowAndColumn. The columns list is sorted. It is traversed and using columnsAndRows, a distinct list of rows for each column distinctRows is produced. This list is traversed and the corresponding list of treenodes nodes are produced using the row:column pair and the map treeNodesByRowAndColumn. This list is traversed to produce an integer list,nodeValues which is added to the final list, answer.The code produced is below.
class Solution {
public List<List<Integer>> verticalTraversal(TreeNode root) {
List<List<Integer>> answer=new ArrayList<>();
List<Integer> columns=new ArrayList<>();
HashMap<Integer,List<Integer>> columnsAndRows=new HashMap<>();
HashMap<TreeNode,List<Integer>> tree=getRowsAndColumns(root,0,0);
HashMap<List<Integer>,List<TreeNode>>treeNodesByRowAndColumn=new HashMap<>();
for(TreeNode key:tree.keySet()){//traverse the map
List<Integer> points=tree.get(key);
int column=points.get(1);
int row=points.get(0);
if(!columns.contains(column))columns.add(column);
if(!columnsAndRows.containsKey(column)){
List<Integer> rows=new ArrayList<>();
rows.add(row);
columnsAndRows.put(column,rows);
}else{
List<Integer> rows=columnsAndRows.get(column);
rows.add(row);
columnsAndRows.replace(column,rows);
}
if(!treeNodesByRowAndColumn.containsKey(points)){
List<TreeNode>nodes=new ArrayList<>();
nodes.add(key);
treeNodesByRowAndColumn.put(points,nodes);
}else{
List<TreeNode>nodes=treeNodesByRowAndColumn.get(points);
nodes.add(key);
treeNodesByRowAndColumn.replace(points,nodes);
}
}
columns.sort(null);
for(int i=0;i<columns.size();i++){//traverse list of columns
List<Integer> values=new ArrayList<>();
List<Integer> rows=columnsAndRows.get(columns.get(i));
List<Integer>distinctRows=rows.stream().distinct().sorted().collect(Collectors.toList());
for(int j=0;j<distinctRows.size();j++ ){//traverse list of distinct rows
List<Integer> point=new ArrayList<>();
point.add(distinctRows.get(j));
point.add(columns.get(i));
List<TreeNode> nodes= treeNodesByRowAndColumn.get(point);
List<Integer> nodeValues=new ArrayList<>();
for(int k=0;k<nodes.size();k++){//traverse list of tree nodes to produce a list of tree values
TreeNode node=nodes.get(k);
int value=node.val;
nodeValues.add(value);
}
nodeValues.sort(null);
values.addAll(nodeValues);
}
answer.add(values);
}
return answer.stream().distinct().collect(Collectors.toList());
}
//recursive dfs function which produces a map of each node and its row and column
public HashMap<TreeNode,List<Integer>> getRowsAndColumns(TreeNode root,int row,int column){
HashMap<TreeNode,List<Integer>> tree=new HashMap<>();
if(root==null) return null;
else if(root.left==null && root.right==null){
List<Integer> point=new ArrayList<>();
point.add(row);
point.add(column);
tree.put(root,point);
return tree;
}else if(root.left==null){
HashMap<TreeNode,List<Integer>>rightSubTree=getRowsAndColumns(root.right,row+1,column+1);
if(rightSubTree!=null)tree.putAll(rightSubTree);
List<Integer> point=new ArrayList<>();
point.add(row);
point.add(column);
tree.put(root,point);
return tree;
}else if(root.right==null){
HashMap<TreeNode,List<Integer>>leftSubTree=getRowsAndColumns(root.left,row+1,column-1);
if(leftSubTree!=null)tree.putAll(leftSubTree);
List<Integer> point=new ArrayList<>();
point.add(row);
point.add(column);
tree.put(root,point);
return tree;
}else{
HashMap<TreeNode,List<Integer>>leftSubTree=getRowsAndColumns(root.left,row+1,column-1);
if(leftSubTree!=null)tree.putAll(leftSubTree);
HashMap<TreeNode,List<Integer>>rightSubTree=getRowsAndColumns(root.right,row+1,column+1);
if(rightSubTree!=null)tree.putAll(rightSubTree);
List<Integer> point=new ArrayList<>();
point.add(row);
point.add(column);
tree.put(root,point);
return tree;
}
}
}
Feel free to comment.