GeeksForGeeks - Vertical Traversal of Tree

link

Problem

Traverse the tree verticall from left to right

Solution

Use bfs and group the nodes in the same vertical axis in order.

void bfs(Node* root, map<int, queue<int>>& mp){
    queue<Node*> q;
    queue<int> axis;
    q.push(root);
    axis.push(0);
    mp[0].push(root->data);
    while(!q.empty()){
        Node* cur = q.front();
        if(cur->left){
            q.push(cur->left);
            int haxis = axis.front() - 1;
            mp[haxis].push((cur->left)->data);
        }
        if(cur->right){
            q.push(cur->right);
            int haxis = axis.front() + 1;
            mp[haxis].push((cur->right)->data);
        }
        
        q.pop();
        axis.pop();
    }
}

vector<vector<int>> verticalOrder(Node* root) {
    map<int, queue<int>> mp;
    bfs(root, mp);
    vector<vector<int>> list(mp.size());

    size_t i = 0;
    for(auto it = mp.begin(); it != mp.end(); ++it){
        list[i].resize((it->second).size());
        size_t j = 0;
        while(!(it->second).empty()){
            list[i][j] = (it->second).front();
            (it->second).pop();
            ++j;
        }
        ++i;
    }
    return list;
}

Time Complexity : O(logn)