Vertical Order Traversal Of A Binary Tree - Leetcode Solution

Problem statement:

Given a binary tree, return the vertical order traversal of its nodes' values. (ie, from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

Examples:

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

3 /
9 20 /
15 7

Output: [ [9], [3,15], [20], [7] ]

Explanation:

• The top-down view of the tree is [9], [3,15], [20], [7]
• In the vertical (column) order traversal, we should first visit the leftmost node (9), then the middle column node (3 and 15), and finally the rightmost node (20 and 7).

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

 1

/
2 3 / \ /
4 5 6 7

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

Explanation:

• The top-down view of the tree is [4], [2], [1,5,6], [3], [7]
• In the vertical (column) order traversal, we should first visit the leftmost node (4), then the left column node (2), then the middle column node (1, 5, and 6), and finally the rightmost node (3 and 7).

Approach:

To solve this problem, we can use map and queue. We can traverse through the tree level by level using a queue and keep track of the columns using a map.

Let's say we have a current node with value val and column index col. We can add this node's value to the column in the map with key col.

• For the left child node, we can add its value to the column col-1.
• For the right child node, we can add its value to the column col+1.
• We also need to keep track of the minimum and maximum column index for all nodes in the tree. This will help us in iterating through the map keys to get the columns in order.

After we have added all the nodes to the map, we can iterate through the map from the minimum column index to the maximum column index and add all the column values to a 2D array, which we will return as the answer.

Solution:

Let's look at the code for the above approach:

C++ Code:

class Solution { public: vector<vector<int>> verticalTraversal(TreeNode* root) {

    // Map to keep all nodes' values in their respective columns
    map<int, vector<pair<int,int>>> m;

    // Queue to traverse the tree level by level
    queue<pair<TreeNode*,pair<int,int>>> q;

    // Starting from the root node with column index 0 and row index 0
    q.push(make_pair(root,make_pair(0,0)));

    // Column minimum and maximum values
    int colMin = INT_MAX, colMax = INT_MIN;

    // Traverse until queue is empty
    while(!q.empty()) {

        // Get values from front of queue
        auto front = q.front();
        q.pop();
        TreeNode* node = front.first;
        int col = front.second.first;
        int row = front.second.second;

        // Add node to map column
        m[col].push_back(make_pair(row,node->val));

        // Update column minimum and maximum values
        colMin = min(colMin,col);
        colMax = max(colMax,col);

        // Insert left child to queue
        if(node->left) q.push(make_pair(node->left,make_pair(col-1,row+1)));

        // Insert right child to queue
        if(node->right) q.push(make_pair(node->right,make_pair(col+1,row+1)));
    }

    // Create result 2D array
    vector<vector<int>> res;

    // Iterate through columns in map
    for(int i=colMin;i<=colMax;i++) {

        // Get all nodes of current column
        auto colNodes = m[i];

        // Sort the nodes based on row and value
        sort(colNodes.begin(),colNodes.end());

        // Add current column nodes to result row
        vector<int> rowNodes;
        for(auto p:colNodes) rowNodes.push_back(p.second);

        // Add current row to result 2D array
        res.push_back(rowNodes);

    }

    return res;
}

};

Time Complexity:

The time complexity of the above solution is O(nlogn), where n is the number of nodes in the tree. This is because we are iterating through the tree level by level, and sorting the nodes in each column, which takes O(logn) time. Since we do this for all n nodes, the overall time complexity is O(nlogn).

Space Complexity:

The space complexity of the above solution is O(n), where n is the number of nodes in the tree. This is because we are using a map to store all nodes in their respective columns, which could have up to n elements in the worst case. Additionally, we are using a queue to traverse the tree level by level, which could have up to n/2 elements in the worst case. Therefore, the overall space complexity is O(n).

1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13public:
14    vector<vector<int>> verticalTraversal(TreeNode* root) {
15        
16        // Base case
17        if (!root) {
18            return {};
19        }
20        
21        // Result vector
22        vector<vector<int>> res;
23        
24        // Queue for BFS
25        queue<pair<TreeNode*, int>> q;
26        
27        // Map for storing the nodes at each horizontal distance
28        map<int, vector<int>> m;
29        
30        // Variable for tracking the minimum horizontal distance
31        int min_hd = 0;
32        
33        // Variable for tracking the maximum horizontal distance
34        int max_hd = 0;
35        
36        // Enqueue the root node with horizontal distance as 0
37        q.push({root, 0});
38        
39        // Loop while queue is not empty
40        while (!q.empty()) {
41            
42            // Get the size of the queue
43            int size = q.size();
44            
45            // Set of values at each horizontal distance
46            // This is required to maintain the order of nodes at same horizontal distance
47            map<int, set<int>> temp;
48            
49            // Loop through all the nodes in the queue
50            for (int i = 0; i < size; i++) {
51                
52                // Dequeue a node from the queue
53                auto node = q.front();
54                q.pop();
55                
56                // Get the horizontal distance of the dequeued node
57                int hd = node.second;
58                
59                // Get the value of the dequeued node
60                int val = node.first->val;
61                
62                // Insert the value in the set at the horizontal distance
63                temp[hd].insert(val);
64                
65                // Update the minimum horizontal distance
66                min_hd = min(min_hd, hd);
67                
68                // Update the maximum horizontal distance
69                max_hd = max(max_hd, hd);
70                
71                // If the dequeued node has a left child, enqueue it
72                if (node.first->left) {
73                    q.push({node.first->left, hd - 1});
74                }
75                
76                // If the dequeued node has a right child, enqueue it
77                if (node.first->right) {
78                    q.push({node.first->right, hd + 1});
79                }
80            }
81            
82            // Loop through the map to insert the nodes at each horizontal distance in the result vector
83            for (int i = min_hd; i <= max_hd; i++) {
84                res.push_back({temp[i].begin(), temp[i].end()});
85            }
86        }
87        
88        return res;
89    }
90};