Print Tree In Vertical Order

Geeks

Description:

Given a binary tree, print it vertically. The following example illustrates vertical order traversal.

Example:

           1
        /    \ 
       2      3
      / \   /   \
     4   5  6   7
               /  \ 
              8   9 


The output of print this tree vertically will be:
4
2
1 5 6
3 8
7
9

Idea:

Preorder traversal, use hashmap to record. key is the level. also record the leftmost and rightmost level.

Code:

// C++ program for printing vertical order of a given binary tree
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
using namespace std;

// Structure for a binary tree node
struct Node
{
    int key;
    Node *left, *right;
};

// A utility function to create a new node
struct Node* newNode(int key)
{
    struct Node* node = new Node;
    node->key = key;
    node->left = node->right = NULL;
    return node;
}

// Code Start // 

void travesalPreorder(Node* root, int level, int& minLevel, int& maxLevel, unordered_map<int, vector<int>>& hashMap){
    if(root==NULL){
        return;
    }
    maxLevel = max(level, maxLevel);
    minLevel = min(level, minLevel);

    hashMap[level].push_back(root->key);

    travesalPreorder(root->left, level-1, minLevel, maxLevel, hashMap);
    travesalPreorder(root->right, level+1, minLevel, maxLevel, hashMap);
}

vector<vector<int>> printVerticalOrder(Node * root){
    unordered_map<int, vector<int>> hashMap;
    vector<vector<int>> result;
    int maxLevel=INT_MIN;
    int minLevel=INT_MAX;
    travesalPreorder(root, 0, minLevel, maxLevel, hashMap);

    for(int i=minLevel; i<=maxLevel; i++){
        result.push_back(hashMap[i]);
    }
    return result;
}

// Code End // 


// Driver program to test above functions
int main()
{
    Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    root->right->left->right = newNode(8);
    root->right->right->right = newNode(9);
    cout << "Vertical order traversal is n\n";
    vector<vector<int>> result = printVerticalOrder(root);
    for(auto elem1: result){
        for(auto elem2: elem1){
            cout<<elem2<<' ';
        }
        cout<<endl;
    }
}