Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
The level-order traversal-based approach
2.1.
Algorithm for the map-based approach
2.2.
Implementation of the map-based approach
3.
Frequently Asked Questions
3.1.
What is the vertical order traversal?
3.2.
How do you vertically print a binary tree using the level order traversal method?
3.3.
How do you know if a binary tree is full?
3.4.
What is the top view of the binary tree?
3.5.
What is level order traversal in a binary tree?
4.
Conclusion
Last Updated: Mar 27, 2024

How to Print a Binary Tree in Vertical Order | Part-3

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

In this blog, we will be discussing the level-order traversal-based method to print a binary tree in vertical order. We already have discussed a few methods like the basic horizontal distance-based method, hashmap, and preorder traversal-based methods to print a binary tree in vertical order in the previous blogs. Check them out to understand these basic methods before diving into the advanced method discussed in this blog.

Let's begin the blog again with a brief introduction of the problem-Suppose we have with the following binary tree, and we are asked to print it in vertical order.

we will get the following output on printing the above binary tree in the vertical order -

9
4
2 6 
5 7 3

11

We can observe from the output that we need to start by printing the leftmost node in the tree, then the next leftmost node, and so on. And if two or more nodes are equally distant from the root, we print them in top-to-bottom order. Since we have understood the problem, let’s move on to the level order traversal-based solution-

Check out these:

The level-order traversal-based approach

This approach to printing a binary tree in vertical order uses a hashmap for each branch of the binary tree. Then it pushes the nodes into a queue while leveling the order traversal of the binary tree. Then we pop the front of the queue and push its values in the map. Finally, we traverse through the map and print the array of nodes stored in it as values. 

Algorithm for the map-based approach

  1. Create a binary tree or take it as input from the user.
  2. Create a map to store horizontal distance and an array of nodes associated with that values of horizontal distance as key-value pairs.
  3. We then create a queue for holding the nodes during the level order traversal of the tree.
  4. We start with pushing the root into the queue with its horizontal distance as 0.
  5. Then we pop the front of the queue and push its values on the map.
  6. Then we make recursive calls for the left and right branches to perform the above steps.
    In the level order traversal of a binary tree, while moving onto the left branch of the tree, the value of horizontal distance decreases by 1 unit, and if we move towards the right branch, the value of horizontal distance increases by 1 unit.  
  7. Finally, we Traverse the map to print all the arrays of nodes stored in the map.

Implementation of the map-based approach

#include <bits/stdc++.h>
using namespace std;
struct node 
{
    int data;
    struct node *left, *right;
};
//To create a new node for the binary tree.
node *createnode(int data)
{
    node *var = new node;
    var->data = data;
    var->left = var->right = NULL;
    return var;
}
//Function to create the map and do the level order 
//traversal of the tree to find vertical order of the 
//nodes and then printing the values in the map.
void printtreevert(node* root)
{
    //Base case.
    if (root==nullptr)
    {
        return;
    }
    //Creat a map to store the node and its 
    //distance in pair.
    map<int,vector<int> > mp;
    int hordist=0;
    //Creating a queue for level order traversal of the 
    //binary tree by holding the node and its horizontal 
    //distance in pair. 
    queue<pair<node*, int> >q;
    q.push(make_pair(root, hordist));
    while(q.empty()!=true)
    {
        //Extracting the value from the top of the queue.
        pair<node*, int>var=q.front();
        q.pop();
        hordist=var.second;
        node* newnode=var.first;
        //pushing the value popped from hashtable into 
        //the map.
        mp[hordist].push_back(newnode->data);
        //Making recursive calls for the left and right 
        //branches of the node.
                if(newnode->left!=nullptr)
        {
            q.push(make_pair(newnode->left, hordist-1));
        }
        if(newnode->right!=nullptr)
        {
            q.push(make_pair(newnode->right, hordist+1));
        }    
    }
    //To print the arrays of the nodes stored in the map.
    map<int, vector<int> >::iterator itr;
    for(itr=mp.begin();itr!=mp.end();itr++)
    {
        for(int i=0;i<itr->second.size();i++)
        {
            cout<<itr->second[i]<<" ";
        }
        cout << endl;
    }
}    
//Driver function.
int main()
{
    //Creating the binary tree.
    node *root=createnode(5);
    root->left=createnode(2);
    root->right=createnode(8);
    root->left->left=createnode(4);
    root->left->right=createnode(7);
    root->right->left=createnode(3);
    root->right->right=createnode(11);
    root->left->left->left=createnode(9);
    root->left->left->right=createnode(6);
    printtreevert(root);
    return 0;
}


Output

9
4
2 6 
5 7 3

11

The time complexity of the above approach is O(N*log(N)), where N is the number of nodes in it, as the map in STL takes O(log(N)) time for all the operations, and we processed all the N nodes.

The space complexity of the above approach is O(N).

Check out this problem - Diameter Of Binary Tree

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is the vertical order traversal?

Vertical order traversal means that we find the different vertical lines in the binary tree, then print the nodes on these from left to right, and the nodes on a vertical line are printed from to bottom.

How do you vertically print a binary tree using the level order traversal method?

To print a binary tree using level order traversal, we traverse through the nodes and push their horizontal distances in a queue along with the nodes. Then we pop the front of the queue, push these values in the map, and make the recursive call for the left and right branches of the tree. Then we traverse the map and print the values stored in it.

How do you know if a binary tree is full?

A full binary tree means that all the nodes in that tree have either zero or two children. We can check it by traversing through the whole tree and checking each node for the condition on the number of child nodes it can have.

What is the top view of the binary tree?

The top view of a binary tree is if we observe the binary from the root point of view. It means that we could only see the nodes which do not have a node above them. You can read more about them here.

What is level order traversal in a binary tree?

In level order traversal of a binary tree, we make sure we traverse through all the nodes in one level of the binary tree before moving on to the next level. We generally use a queue data structure for the level order traversal of the binary tree.

Conclusion

In this blog, we discussed the level order traversal-based method to print a binary tree in vertical order- 

We start with creating a map that will hold the horizontal distance and the nodes as key-value pairs. Then we declare a queue for storing the nodes while leveling the order traversal of the tree. Initially, we push the root node with a horizontal distance of zero. We then pop the front of the queue and push it into the map. Then we recursively repeat the process for the left and right branches of the node popped from the queue. Finally, we traverse through the map and print all the arrays of the nodes stored in it.

Make sure to read other parts of this blog to learn the basic, map, and preorder traversal-based approaches to solving this problem. Also, you can increase your problem-solving skills by practicing similar problems on Coding Ninjas Studio.

Recommended Reading:

 

Recommended problems -

 

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Previous article
How to Print a Binary Tree in Vertical Order | Part-2
Next article
Density Of Binary Tree In One Traversal
Live masterclass