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);
}

Comment