Reference: LeetCode
Difficulty: Medium

Problem

Given a binary tree, return the vertical order traversal of its nodes values.
For each node at position (X, Y), its left and right children respectively will be at positions (X - 1, Y - 1) and (X + 1, Y - 1).
Running a vertical line from X = -infinity to X = +infinity, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing Y coordinates).
If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.
Return an list of non-empty reports in order of X coordinates. Every report will have a list of values of nodes.

Example: 

1
2
Input: [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]

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

Analysis

Methods:

  1. HashMap + TreeMap + PQ (reference)
    • Use a HashMap to record X, and record minX and maxX for future iteration.
      • Why? Because HashMap gets the key in constant time, while TreeMap needs $O(\log{N})$.
      • And also notice that the values of X is continuous. So we can iterate over the map easily if we have minX and maxX.
    • Use a TreeMap to record Y, and use a PriorityQueue to keep nodes with same (x, y) in ascending order.
      • Y is not continuous. We use keySet() in TreeMap to return keys in ascending order, so we can traverse all Y given a specific X.
    • Since some nodes have the same position and we care about their ordering, we use PriorityQueue.
      • It turns out that we can also use ArrayList, and the time complexity does not differ very much. If using ArrayList, remember to sort it manually.
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
// Use HashMap to store X
// Use TreeMap to store Y
// If some nodes have same (X, Y), they are in the Priority Queue.
Map<Integer, TreeMap<Integer, PriorityQueue<Integer>>> map = new HashMap<>();
int minX = 0, maxX = 0;

public List<List<Integer>> verticalTraversal(TreeNode root) {
  buildMap(root, 0, 0);
  List<List<Integer>> result = new ArrayList<>();
  // For each X
  for (int x = minX; x <= maxX; ++x) {
    List<Integer> level = new ArrayList<>();
    // For each Y (in order bc TreeMap)
    for (int y : map.get(x).keySet()) {
      PriorityQueue<Integer> pq = map.get(x).get(y);
      while (pq.size () > 0) {
        level.add(pq.poll());
      }
    }
    result.add(level);
  }
  return result;
}


private void buildMap(TreeNode node, int x, int y) { // traverse each node O(N)
  if (node == null) {
    return;
  }
  // record min & max
  minX = Math.min(minX, x);
  maxX = Math.max(maxX, x);
    
  if (map.get(x) == null) { // Init TreeMap
    map.put(x, new TreeMap<Integer, PriorityQueue<Integer>>());
  }
  if (map.get(x).get(y) == null) { // Init PQ
    map.get(x).put(y, new PriorityQueue<Integer>()); // O(log(h))
  }
  PriorityQueue<Integer> pq = map.get(x).get(y);
  pq.add(node.val); // log
  
  // recursive
  helper(node.left, x - 1, y + 1);
  helper(node.right, x + 1, y + 1);
}

Time: $O(N\log{N})$ for each node the runtime could be upper bounded by $O(\log{N})$.
Space: $O(N)$

Review code:

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
Map<Integer, Map<Integer, PriorityQueue<Integer>>> map;
int minX = 0;
int maxX = 0;

public List<List<Integer>> verticalTraversal(TreeNode root) {
  if (root == null) {
    return null;
  }
  map = new HashMap<>();
  buildMap(root, 0, 0);
  // Iterate map
  List<List<Integer>> result = new ArrayList<>();
  for (int x = minX; x <= maxX; ++x) {
    List<Integer> list = new ArrayList<>();
    Map<Integer, PriorityQueue<Integer>> treeMap = map.get(x);
    for (Integer y : treeMap.keySet()) { // in order
      PriorityQueue<Integer> pq = treeMap.get(y);
      while (pq.size() > 0) {
        list.add(pq.poll());
      }
    }
    result.add(list);
  }
  return result;
}

private void buildMap(TreeNode root, int x, int y) {
  if (root == null) {
    return;
  }
  // root
  minX = Math.min(minX, x);
  maxX = Math.max(maxX, x);
  Map<Integer, PriorityQueue<Integer>> treeMap = map.getOrDefault(x, new TreeMap<>());
  PriorityQueue<Integer> pq = treeMap.getOrDefault(y, new PriorityQueue<>());
  pq.add(root.val);
  // set back
  treeMap.put(y, pq);
  map.put(x, treeMap);
  
  // left
  buildMap(root.left, x - 1, y + 1);
  // right
  buildMap(root.right, x + 1, y + 1);
}