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).
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.