I'm trying to solve the problem of Vertical Order Traversal of Binary Tree using map and queue. I did solve it using a recursive way, but I'm not getting the same answer using the iterative way.

       10
     /    \
    7      4
  /  \    /  \
 3   11  14   6

Approach :

First I declared an integer that stores horizontal distance from the root node.

Horizontal distance means that the left part from the root will be considered as -1, -2 and so on, like a negative X axis, where the root is origin and starts from 0. So node 7 will be given -1, 3 will be given -2. However, 10, 11, 14 will be given 0 as they are not away from root node but lie in the same position. And towards the right, distance will become positive so 4 will get distance 1, 6 will get 2 and so on.

At first, I pushed the root in the queue and updated the horizontal distance as 0. After that, I added horizontal distance as key and root data as value in the map. And finally, I poped the root from the queue and I checked for its left and right child, if left or right child was available, I pushed the left and right child in the queue respectively and updated horizontal distance accordingly. Then I followed the same procedure for the complete binary tree.

And then, I just traversed through the second part of the map to get the answer.

The Answer should be :
3 
7 
10 11 14 
4 
6 

The Answer I received is : 
10 7 4 3 11 14 6 

Here is my Code :

#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;

struct Node
{
    int data;
    Node *left;
    Node *right;

    Node(int val)
    {
        data = val;
        left = NULL;
        right = NULL;
    }
};

map<int, vector<int>> verticalPrint(Node *root)
{
    queue<Node *> qi;
    map<int, vector<int>> mp;

    int Hd = 0;
    qi.push(root);

    while (!qi.empty())
    {
        Node *temp = qi.front();
        mp[Hd].push_back(temp->data);
        qi.pop();

        if (temp->left != NULL)
        {
            qi.push(temp->left);
            Hd -= 1;
        }
        if (temp->right != NULL)
        {
            qi.push(temp->right);
            Hd  = 1;
        }
    }
    return mp;
}

int main()
{
    Node *root = new Node(10);
    root->left = new Node(7);
    root->right = new Node(4);
    root->left->left = new Node(3);
    root->left->right = new Node(11);
    root->right->left = new Node(14);
    root->right->right = new Node(6);

    map<int, vector<int>> mp = verticalPrint(root);

    map<int, vector<int>>::iterator it;

    for (it = mp.begin(); it != mp.end(); it  )
    {
        for (int i = 0; i < it->second.size(); i  )
        {
            cout << it->second[i] << " ";
        }
        cout << endl;
    }

    return 0;
}

CodePudding user response：

You cannot use a single Hd variable like that. Note how in the first iteration, Hd will go to -1 and back to 0 because the root has both a left and right child. So in the next iteration you start again with 0, yet the node that you pull from the queue has nothing to do with that value of Hd.

Instead, put pairs in the queue: a combination of node and its corresponding horizontal distance. Then it will work fine:

map<int, vector<int>> verticalPrint(Node *root)
{
    queue<pair<int, Node *>> qi;
    map<int, vector<int>> mp;

    qi.push({0, root});

    while (!qi.empty())
    {
        pair<int, Node*> item = qi.front();
        int hd = item.first;
        Node * temp = item.second;
        mp[hd].push_back(temp->data);
        qi.pop();

        if (temp->left != NULL)
        {
            qi.push({hd - 1, temp->left});
        }
        if (temp->right != NULL)
        {
            qi.push({ hd 1, temp->right});
        }
    }
    return mp;
}