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

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-

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 -

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. 

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;
}

You can also try this code with Online C++ Compiler

Run Code

Output