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

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

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

In this blog, we will be discussing map and preorder traversal-based methods to print a binary tree in vertical order. We already have the basic method to print a binary tree in vertical order in this blog. Check it out to learn the basic method and understand the problem thoroughly.  

Also see, Iterative Preorder Traversal of Trees

Before diving into the solution, let's again have a brief look at the problem. Suppose we have the following binary tree, and we need to print it in vertical order.

illustration image

 

On printing the binary tree given above, we will get the following output -

9
4
2 6 
5 7 3

1

We can observe from the output that we need to print 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. Though the map-based solution is faster, it couldn't fulfill this criterion. We will learn another approach based on the preorder traversal of a binary tree, which fulfills this criterion. So, let's begin with the map-based method. 

The map-based approach

This approach to printing a binary tree in vertical order uses a hashmap of vectors of horizontal distance vs. an array of nodes having equal horizontal distance values. So, we start with traversing the tree, finding each node's horizontal distance, and inserting them into the map by appending them to the array corresponding to their key's value. Then we iterate through the map in the increasing order of the keys and print the array of associated nodes.

Algorithm for the map-based approach

  • Create a binary tree or take it as input from the user.
  • Create a map to store horizontal distance and an array of nodes with that distance as key-value pairs.
  • Traverse the tree and keep appending nodes in the array associated with their distance from the root.
  • 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 find the nodes at a hordist and push 
//them in to the map.
void togetverticalorder(node* root, int hordist, map<int, vector<int>>&mp)
{
    //Base case.
    if(root==nullptr)
    {
        return;
    }
    //To push the node into the vector corresponding 
    //to its hoizontal distance.
    mp[hordist].push_back(root->data);
    //Make recursive calls for the left and right 
    //subtrees.
    togetverticalorder(root->left, hordist-1, mp);
    togetverticalorder(root->right, hordist+1, mp);
}
//Function to create a map, then get the vertical 
//order of the tree by calling above function, then 
//printing. 
void vertiorder(node *root)
{
    //Creating a map.
    map<int,vector<int>> mp;
    int hordist=0;
    togetverticalorder(root, hordist, mp);
    //To print the values 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);
    vertiorder(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).

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

The preorder traversal-based method

In the previous method, we could not maintain the top-to-bottom order of printing the nodes with the same horizontal distance. So, to handle it, we can use a solution based on the preorder traversal of the binary tree.

In this method, we find both horizontal and vertical distances of the nodes from the tree’s root to decide the order in which they will get stored in the map, thus helping us maintain their order of appearance in the binary tree.

The idea is to create a map of distance from the root vs. an array of nodes as key-value pairs. The key values are stored by first assigning them the horizontal distance, then right-shift them by 30 places, and then taking its bitwise “or” with the vertical distance of the node from the root. And as we know, the map stores keys in ascending order; thus, the key with a smaller vertical distance will always appear first while traversing the map.

Algorithm for preorder traversal-based method

  • Create a binary tree or take it as input from the user.
  • Create a map to store the distance of the nodes(horizontal+vertiical) vs. an array of nodes with that distance.
  • Traverse the tree to find the horizontal and vertical distance of the nodes by left-shifting the horizontal distance and taking bitwise or vertical distance. The first half of the binary number represents the horizontal distance, and the second half represents the vertical distance.
  • Then traverse the map to print all the arrays of nodes stored in the map.

Implementation of preorder traversal-based method

#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 find the horizontal and vertical distances and push them into the map.
void traversal(node* root, long long int hordist, long long int verdist, map<long long int, vector<int>>&mp)
{
    //Base case.
    if(root==nullptr)
    {
            return;
    }
    //To modify the key so that it contains a 
    //combined value of horizontal and vertical 
    //distance.
    long long int key=hordist<<30|verdist;
    //To push the nodes into the vector 
    //corresponding to its distance from the root.
    mp[key].push_back(root->data);
    //Make recursive calls for the left and right 
    //subtrees.
    traversal(root->left, hordist-1, verdist+1, mp);
    traversal(root->right, hordist+1, verdist+1, mp);
}
//Function to create a map, then call the above function and printing the map.
void vertiorder(node *root)
{
    //Creating a map.
    map<long long int,vector<int>> mp;
    traversal(root, 0, 1, mp);
    //To print the pairs in the map.
    //We also use a temp value intitalised to know 
    //whether the next key in the map is of the same 
    //vertical order as the last one or of a new 
    //vertical order. 
    int temp=INT_MAX;
    map<long long int,vector<int> > :: iterator itr;
    for(itr=mp.begin(); itr!=mp.end(); itr++)
    {
        //To move to new line when we finish 
        //printing a vertical order.
        if(temp != INT_MAX &&( itr->first>>30)!=temp)
        {
            cout << endl;
        }
        //To print all the nodes with same vertical 
        //and horizontal order.
        temp = itr->first >> 30;
        for(int i=0;i<itr->second.size();++i)
            cout << itr->second[i] << " ";
    }
}
//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);
    vertiorder(root);
    return 0;
}


Output-

9
4
2 6 
5 7 3

11

The time complexity of the above approach is O(N*log(N)).

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

Check out this problem - Diameter Of Binary Tree

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 maps?

To print a binary tree using maps, we store the horizontal and an array of nodes corresponding to that distance as key-value pairs in the map, then traverse the map to print all the key-value pairs 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 preorder traversal in a binary tree?

In the preorder traversal of a tree, we always process the root, then process the left subtree of the root, then the right subtree of the root. 

Conclusion

In this blog, we discussed a map-based and another preorder traversal-based method to print a binary tree in vertical order- 

  • We first discussed a hash map-based approach which will have the horizontal distance of nodes as keys and maintain an array of nodes associated with it. Then we traverse the tree and keep inserting nodes into the map. Then we traverse the map and print all the nodes stored in it. The only problem with this solution is that we can't maintain the top-to-bottom order for the nodes with the same horizontal distance.
     
  • The second method we discussed was based on the preorder traversal of the binary tree. This method maintains the top to bottom order for the nodes with the same horizontal distance. For this, we modify the way we store the keys on the map. We first assign the horizontal distance to the key, then left-shift it and take the bitwise “or” with the vertical distance. So, half of it denotes the horizontal distance of the node, and half of it denotes the vertical distance from the root. Since the map stores the keys in the sorted order, the key with equal horizontal distance get stored in the top to bottom order. Then we print the array in the map, thus printing the given binary tree in vertical order.
     

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-1
Next article
How to Print a Binary Tree in Vertical Order | Part-3
Live masterclass