Print Binary tree in vertical order

Problem Statement

Given a Binary tree, print it in vertical order from left to right.

Binary Tree

Vertical order for the above Binary tree is:

Vertical order
Vertical order(root):
2 
3 1 
5 4 
7
8

We could solve this problem by performing a breadth-first or level order traversal on the given tree and using a variable ‘level’ to store nodes at same vertical level together in a hash map.

Pseudocode
1. Initialise queue: Q.push (pair(root, level))
2. While !Q.empty()
3.   node = Q.pop() 
4.   node* temp = node.first
5.   int level = node.second
6.   map[level].push(temp->value)
7. Iterate over map to print vertical order

Time complexity: O(nlogn)
Auxiliary Space: O(n)

Time complexity could be improved to O(n), if we use a map implementation that allow us O(1) lookups. The C++ map that is used above has O(logn) time complexity.

Code Implementation
//
//  main.cpp
//  Print Binary Tree Vertically
//
//  Created by Himanshu on 25/09/21.
//

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

struct node {
    int value = 0;
    struct node *left, *right;
};
typedef struct node Node;

node* newNode(int data)
{
    node* Node = new node();
    Node->value = data;
    Node->left = NULL;
    Node->right = NULL;
 
    return(Node);
}

void printVertically (Node *root) {
    if (root == NULL) {
        return;
    }
    
    map<int, vector<int>> hmap;
    map<int, vector<int>>::iterator it;
    queue<pair<Node*, int>> qu;
    int level = 0;
    
    qu.push(make_pair(root, level));
    
    while (!qu.empty()) {
        int size = (int) qu.size();
        for (int i=0; i<size; i++) {
            pair<Node*, int> node = qu.front();
            qu.pop();
            Node *temp = node.first;
            level = node.second;
            
            hmap[level].push_back(temp->value);
            
            if (temp->left) {
                 qu.push(make_pair(temp->left, level-1));
            }
            if (temp->right) {
                qu.push(make_pair(temp->right, level+1));
            }
        }
        level++;
    }
    
    for (it = hmap.begin(); it != hmap.end(); it++) {
        for (int j = 0; j < it->second.size(); j++) {
            cout << it->second[j] << " ";
        }
        cout << endl;
    }
}

int main() {
    Node *root = newNode(5);
    root->left = newNode(3);
    root->right = newNode(7);
    root->left->left = newNode(2);
    root->left->right = newNode(4);
    root->left->left->right = newNode(1);
    root->right->right = newNode(8);
    
    cout<<"Vertical order:"<<endl;
    printVertically (root);
    return 0;
}

Output

Vertical order:
2 
3 1 
5 4 
7 
8 

Here’s a working example:

https://ideone.com/lZC7on

Leave a Reply

Your email address will not be published.