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