Solution For Vertical Order Traversal Of A Binary Tree

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> 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).

Step by Step Implementation For Vertical Order Traversal Of A Binary Tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List> verticalOrder(TreeNode root) {
        
        // check for empty tree
        if (root == null) {
            return new ArrayList<>();
        }
        
        // create a map to store the vertical order traversal
        Map> map = new TreeMap<>();
        
        // create a queue for Breadth First Search
        Queue queue = new LinkedList<>();
        Queue cols = new LinkedList<>();
        
        // start the BFS from the root node
        queue.add(root);
        cols.add(0);
        
        // run till queue is not empty
        while (!queue.isEmpty()) {
            
            // remove the front element from the queue
            TreeNode node = queue.poll();
            int col = cols.poll();
            
            // if this column is not present in the map, then create a new list
            if (!map.containsKey(col)) {
                map.put(col, new ArrayList<>());
            }
            
            // add the node to the map
            map.get(col).add(node.val);
            
            // if the node has a left child, add it to the queue
            if (node.left != null) {
                queue.add(node.left);
                cols.add(col - 1);
            }
            
            // if the node has a right child, add it to the queue
            if (node.right != null) {
                queue.add(node.right);
                cols.add(col + 1);
            }
        }
        
        // return the vertical order traversal of the tree
        return new ArrayList<>(map.values());
    }
}

from collections import defaultdict 
  
# A utility function to create a new node 
class Node: 
    def __init__(self, key): 
        self.data = key  
        self.left = None
        self.right = None
  
# Function to Build Tree   
def buildTree(string): 
    # Corner Case 
    if(string[0] == "N"): 
        return None
  
    # Creating list of strings from input 
    # string after spliting by space 
    ip = list(map(str, string.split())) 
      
    # Create the root of the tree 
    root = Node(int(ip[0]))  
    size = 0
    q = [root] 
      
    # Starting from the second element 
    i = 1
    while(size > 0 and i < len(ip)): 
        # Get and remove the front of the queue 
        currNode = q[0] 
        q.pop(0) 
        size = size-1
  
        # Get the current node's value from the string 
        currVal = ip[i] 
  
        # If the left child is not null 
        if(currVal != "N"): 
              
            # Create the left child for the current node 
            currNode.left = Node(int(currVal)) 
              
            # Push it to the queue 
            q.append(currNode.left) 
            size = size+1
        # For the right child 
        i = i+1
        if(i >= len(ip)): 
            break
        currVal = ip[i] 
          
        # If the right child is not null 
        if(currVal != "N"): 
              
            # Create the right child for the current node 
            currNode.right = Node(int(currVal)) 
              
            # Push it to the queue 
            q.append(currNode.right) 
            size = size+1
        i = i+1
    return root 
  
def verticalOrder(root): 
    # Base case 
    if root is None: 
        return
  
    # Create empty queues for 
    #  level order traversal 
    dict = defaultdict(list) #dictionary that stores the nodes at each horizontal distance
    hd = 0 #horizontal distance of the root
    queue = [] #queue for level order traversal
  
    # Enqueue Root and initialize HD as 0 
    queue.append(root) 
  
    while(len(queue) > 0): 
        # Extract the node at the front of 
        #  the queue and its horizontal 
        # distance from the root 
        temp = queue.pop(0) 
        hd = temp.hd 
  
        # Add the extracted node to the 
        # dictionary dict
        dict[hd].append(temp.data) 
  
        # Enqueue left and right children 
        if temp.left: 
            temp.left.hd = hd-1
            queue.append(temp.left) 
          
        if temp.right: 
            temp.right.hd = hd+1
            queue.append(temp.right) 
    # Traverse the dictionary and print nodes at 
    #  each horizontal distance (hd) 
    for index, value in sorted(dict.items()): 
        for i in value: 
            print(i, end=" ") 
        print() 
  
if __name__ == '__main__': 
    t = int(input()) 
  
    for i in range(t): 
        string = input() 
        root = buildTree(string) 
        verticalOrder(root) 
        print()

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var verticalOrder = function(root) {
    if(!root) return [];
    
    let map = {};
    let queue = [[root, 0]];
    let min = 0;
    let max = 0;
    
    while(queue.length) {
        let [node, col] = queue.shift();
        if(!map[col]) map[col] = [node.val];
        else map[col].push(node.val);
        min = Math.min(min, col);
        max = Math.max(max, col);
        if(node.left) queue.push([node.left, col - 1]);
        if(node.right) queue.push([node.right, col + 1]);
    }
    
    let ans = [];
    for(let i = min; i <= max; i++) {
        ans.push(map[i]);
    }
    return ans;
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector> verticalTraversal(TreeNode* root) {
        
        // Base case
        if (!root) {
            return {};
        }
        
        // Result vector
        vector> res;
        
        // Queue for BFS
        queue> q;
        
        // Map for storing the nodes at each horizontal distance
        map> m;
        
        // Variable for tracking the minimum horizontal distance
        int min_hd = 0;
        
        // Variable for tracking the maximum horizontal distance
        int max_hd = 0;
        
        // Enqueue the root node with horizontal distance as 0
        q.push({root, 0});
        
        // Loop while queue is not empty
        while (!q.empty()) {
            
            // Get the size of the queue
            int size = q.size();
            
            // Set of values at each horizontal distance
            // This is required to maintain the order of nodes at same horizontal distance
            map> temp;
            
            // Loop through all the nodes in the queue
            for (int i = 0; i < size; i++) {
                
                // Dequeue a node from the queue
                auto node = q.front();
                q.pop();
                
                // Get the horizontal distance of the dequeued node
                int hd = node.second;
                
                // Get the value of the dequeued node
                int val = node.first->val;
                
                // Insert the value in the set at the horizontal distance
                temp[hd].insert(val);
                
                // Update the minimum horizontal distance
                min_hd = min(min_hd, hd);
                
                // Update the maximum horizontal distance
                max_hd = max(max_hd, hd);
                
                // If the dequeued node has a left child, enqueue it
                if (node.first->left) {
                    q.push({node.first->left, hd - 1});
                }
                
                // If the dequeued node has a right child, enqueue it
                if (node.first->right) {
                    q.push({node.first->right, hd + 1});
                }
            }
            
            // Loop through the map to insert the nodes at each horizontal distance in the result vector
            for (int i = min_hd; i <= max_hd; i++) {
                res.push_back({temp[i].begin(), temp[i].end()});
            }
        }
        
        return res;
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList> VerticalTraversal(TreeNode root) {
        
        //Create a dictionary to store the vertical order traversal
        Dictionary> dict = new Dictionary>();
        
        //Create a queue to do a level order traversal
        Queue queue = new Queue();
        Queue cols = new Queue();
        
        //Start the traversal from the root node
        queue.Enqueue(root);
        cols.Enqueue(0);
        
        //Loop through the queue while it's not empty
        while(queue.Count != 0){
            //Get the size of the queue
            int size = queue.Count;
            
            //Create a list to store the nodes at the same horizontal distance
            List list = new List();
            
            //Loop through the queue
            for(int i = 0; i < size; i++){
                //Get the node at the front of the queue
                TreeNode node = queue.Dequeue();
                
                //Get the column value of the node
                int col = cols.Dequeue();
                
                //Check if the column value is in the dictionary
                if(!dict.ContainsKey(col)){
                    //If it's not, add it to the dictionary
                    dict.Add(col, new List());
                }
                
                //Add the node to the list
                list.Add(node.val);
                
                //Check if the node has a left child
                if(node.left != null){
                    //If it does, add it to the queue
                    queue.Enqueue(node.left);
                    
                    //Add the column value - 1 to the queue
                    cols.Enqueue(col - 1);
                }
                
                //Check if the node has a right child
                if(node.right != null){
                    //If it does, add it to the queue
                    queue.Enqueue(node.right);
                    
                    //Add the column value + 1 to the queue
                    cols.Enqueue(col + 1);
                }
            }
            
            //Add the list of nodes to the dictionary
            dict.Add(col, list);
        }
        
        //Create a list to store the final result
        List> result = new List>();
        
        //Loop through the dictionary
        foreach(var key in dict.Keys){
            //Add the list of nodes at the same horizontal distance to the final result
            result.Add(dict[key]);
        }
        
        //Return the final result
        return result;
    }
}