Leetcode 987. Vertical Order Traversal of a Binary Tree

Problem Explanation:

This problem on vertical order traversal of a binary tree requires you to return a list of nodes' vertical order traversal.

Each node in binary tree has a position (X,Y). If the position of root node is (0,0),

• Position for left child will be (X-1, Y-1)
• Position for right child will be (X+1, Y-1)

We execute a vertical line from X = -infinity to X = +infinity. All nodes that this vertical line touches are included in the report. The nodes are included in the order from top to bottom (i.e. decreasing Y-coordinates). In a situation where two nodes occupy the same position, the node with the smaller value is reported first.

Our aim is to return a list of non-empty reports in X-coordinate order.

Let's consider an example: For the binary tree [3,9,20,null,null,15,7], the output will be [[9],[3,15],[20],[7]]. Here, the positioning would be as follows:

• the node with value 9 at position (-1, -1);
• the nodes with values 3 and 15 at positions (0, 0) and (0, -2);
• the node with value 20 at position (1, -1);
• the node with value 7 at postion (2, -2).

Solution Approach:

The solution to this problems uses the DFS (depth-first-search) traversing strategy.

We declare a map xToSortedPairs where key is x and value is sorted pairs of (-y,val).

A depth-first traversal is performed where we calculate and store the x and y coordinated for each node in the xToSortedPairs map. Everytime during dfs operation, we insert the nodes in the multiset according to (y, root->val) pair.

Lastly, we iterate over this map to push the sorted nodes (sorted based on y-coordinates) for every x in the resultant vector(ans).

C++ Solution:

1
2c++
3class Solution {
4 public:
5  vector<vector<int>> verticalTraversal(TreeNode* root) {
6    vector<vector<int>> ans;
7    map<int, multiset<pair<int, int>>> xToSortedPairs;  // {x: {(-y, val)}}
8
9    dfs(root, 0, 0, xToSortedPairs);
10
11    for (const auto& [_, pairs] : xToSortedPairs) {
12      vector<int> vals;
13      for (const pair<int, int>& pair : pairs)
14        vals.push_back(pair.second);
15      ans.push_back(vals);
16    }
17
18    return ans;
19  }
20
21 private:
22  void dfs(TreeNode* root, int x, int y,
23           map<int, multiset<pair<int, int>>>& xToSortedPairs) {
24    if (root == nullptr)
25      return;
26
27    xToSortedPairs[x].emplace(y, root->val);
28    dfs(root->left, x - 1, y + 1, xToSortedPairs);
29    dfs(root->right, x + 1, y + 1, xToSortedPairs);
30  }
31};

Python Solution:

1
2python
3from collections import defaultdict
4import heapq
5class Solution:
6    def verticalTraversal(self, root):
7        heap = []
8        def dfs(node, x, y):
9            if node is None:
10                return
11            heapq.heappush(heap, (x, -y, node.val))
12            dfs(node.left, x-1, y-1)
13            dfs(node.right, x+1, y-1)
14
15        dfs(root, 0, 0)
16        ans, prior_x = [], None
17        while heap:
18            x, y, val = heapq.heappop(heap)
19            if x != prior_x:
20                prior_x = x
21                ans.append([])
22            ans[-1].append(val)
23        return ans

JavaScript Solution:

1
2javascript
3var verticalTraversal = function(root) {
4    const nodeInfos = [];
5    getNodeInfos(root, 0, 0);
6
7    nodeInfos.sort((a, b) => {
8        if (a.x !== b.x) return a.x - b.x;
9        else if (a.y !== b.y) return a.y - b.y;
10        else return a.val - b.val;
11    });
12
13    let curXAxix = nodeInfos[0].x;
14    let col = [];
15    const res = [col];
16    for (let {x, val} of nodeInfos) {
17        if (x === curXAxix) {
18            col.push(val);
19        } else {
20            curXAxix = x;
21            col = [val];
22            res.push(col);
23        }
24    }
25    return res;
26
27    function getNodeInfos(node, x, y) {
28        if (node) {
29            nodeInfos.push({x, y, val: node.val});
30            getNodeInfos(node.left, x - 1, y + 1);
31            getNodeInfos(node.right, x + 1, y + 1);
32        }
33    }
34};

Java Solution:

1
2java
3class Solution {
4    List<Location> locations;
5    public List<List<Integer>> verticalTraversal(TreeNode root) {
6        locations = new ArrayList();
7
8        dfs(root, 0, 0);
9
10        Collections.sort(locations);
11
12        List<List<Integer>> ans = new ArrayList();
13        ans.add(new ArrayList<Integer>());
14
15        int prev_x = locations.get(0).x;
16
17        for (Location loc: locations) {
18            if (loc.x != prev_x) {
19                prev_x = loc.x;
20                ans.add(new ArrayList<Integer>());
21            }
22
23            ans.get(ans.size() - 1).add(loc.val);
24        }
25        return ans;
26    }
27
28    public void dfs(TreeNode node, int x, int y) {
29        if (node != null) {
30            locations.add(new Location(x, y, node.val));
31            dfs(node.left, x-1, y+1);
32            dfs(node.right, x+1, y+1);
33        }
34    }
35}
36
37class Location implements Comparable<Location> {
38    int x, y, val;
39    Location(int x, int y, int val) {
40        this.x = x;
41        this.y = y;
42        this.val = val;
43    }
44
45    public int compareTo(Location that) {
46        if (this.x != that.x)
47            return Integer.compare(this.x, that.x);
48        else if (this.y != that.y)
49            return Integer.compare(this.y, that.y);
50        else
51            return Integer.compare(this.val, that.val);
52    }
53}

These python, java and javascript solutions use depth-first-search traversal and then sort nodes based on x and y coordinated before adding them to the result array. The major time complexity comes from sorting which is O(n log n).