Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
The basic approach
2.1.
Implementation of the basic approach
3.
 
4.
Frequently Asked Questions
4.1.
What is the vertical order traversal?
4.2.
How do you vertically print a binary tree?
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 are cousins in a binary tree?
5.
Conclusion
Last Updated: Mar 27, 2024

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

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 a programming problem in which we have to print a binary tree in vertical order. Before moving on to the solution, let's have a look at an example to understand the problem thoroughly-

Tree

To print the above binary tree in vertical order, we need to find the group of nodes at an equal horizontal distance from the root(left/right). Then, we begin printing these groups of nodes while moving from left to right, and in case there are two or more nodes at the same level, we print them from top to bottom. So, if we print the above binary tree in vertical order, the output will be as follows -

9
4
2 6 
5 7 3

1

There could be numerous approaches to solving this problem, But we will only be discussing some of the most efficient and well-known methods for this problem. Though this blog will focus on the basic approach to printing a binary tree in vertical order, the optimized approaches are discussed in the second and third parts of this blog.

Also see, Data Structures

The basic approach

This approach to printing a binary tree in vertical order starts with finding the horizontal distance of each node from the root while keeping track of the highest and lowest value of the horizontal distance for the tree. 

We imagine drawing a vertical line whenever we get a node, and if two more nodes are at the same distance, they are said to be sharing the same line. Then we print the nodes at all the vertical lines starting from the one at the minimum distance. 

One important thing to remember is that we consider the distance traveled on the left from the tree's root to be negative and the distance traveled on the right to be positive.  

Consider the example given earlier; the black lines depict the vertical lines, with their corresponding horizontal distance from the root. 

illustration image


Algorithm for the basic approach-

  • Create a binary tree or take it as input from the user.
  • Find the horizontal distance of each node from the root using recursion, and get the minimum and maximum value of the distance.
  • Traverse through the tree and compare the distance of each node to check-
    • If the distance is lesser than the minimum distance, update the minimum distance.
    • If the distance is greater than the maximum distance, update the maximum distance.
  • Then we print the nodes on vertical lines. We start from the vertical line with a minimum distance and keep doing until we reach the maximum distance.

Implementation of the basic 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 maximum and minimum distance.
void getextremes(node *tnode, int *minimumd, int *maximumd, int hordist)
{
    //Base case.
    if(tnode==nullptr)
    {
        return;
    }
    //Update minimum distance or maximum distance if a node with
    
    //smaller or greater value is encountered respectively. 
    if(hordist<*minimumd)
    {
        *minimumd = hordist;
    }
    else if(hordist>*maximumd)
    {
        *maximumd = hordist;
    }
    //Making recursive calls for left and right subtrees.
    getextremes(tnode->left, minimumd, maximumd, hordist-1);
    getextremes(tnode->right, minimumd, maximumd, hordist+1);
}
//Function to print the nodes present on a given vertical line.
void printvl(node *node, int lno, int hordist)
{
    //Base case.
    if(node==nullptr)
    {
        return;
    }
    //Print the node if it lies on the line.
    if(hordist==lno)
    {
        cout<<node->data<<" ";
    }
    //Make recursive  calls for the left and right subtree as well.
    printvl(node->left, lno, hordist-1);
    printvl(node->right, lno, hordist+1);
}

//Function to find the extreme values of horizontal distance, and //then iterate through the tree and printing nodes in the vertical //order.
void vertiorder(node *root)
{
    int minimumd=0,maximumd=0;
    //Function call to find the extreme values of horizontal distance.
    
    getextremes(root, &minimumd, &maximumd, 0);
    for(int lno=minimumd; lno<=maximumd; lno++)
    {
        //Function call to print nodes on a given vertical line.
        printvl(root, lno, 0);
        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

 

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

 

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, the nodes on a vertical line are printed from to bottom. 

How do you vertically print a binary tree?

There are numerous methods to vertically print a binary we can use the basic horizontal distance method or hashmap method and many more. The basic idea is to find the equidistant nodes, then print them from left to right and top to bottom.

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 are cousins in a binary tree?

If two nodes are at the same level but have different parents in a binary tree, they are called cousins.

Conclusion

In this blog, we discussed the basic approach to printing a binary tree in vertical order-

The basic approach is based on finding the groups of nodes in the tree at an equal horizontal distance. These groups are called vertical lines. We also keep track of the line at maximum and minimum distances. Then, we print the nodes on these lines starting with the line at a minimum distance, and if a vertical line has two or more nodes, we print them from top to bottom.

The solution discussed in this blog is the naive approach. So, make sure to read the second and third parts of this blog to learn the advanced optimized approaches. Also, practice 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, Computer Networks, DBMS, System Design, 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
Traversal in Binary Tree
Next article
How to Print a Binary Tree in Vertical Order | Part-2
Live masterclass