Print a Binary Tree in Vertical Order

PROBLEM :

Given a binary tree, print it vertically. The following example illustrates vertical order traversal.

           1
        /    \
       2      3
      / \    / \
     4   5  6   7
             \   \
              8   9
             

The output of print this tree vertically will be:
4
2
1 5 6
3 8
7
9
   
--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------

/*
typedef struct BST
{
int info ;
struct BST *left ;
struct BST *right ;
}tree ;---------------------------------------------*/

void find_MinMax_Vdist(tree *,int *,int *,int ) ;
void Print_Vertical_Order(tree *,int ,int ) ;

void Vertical_Order(tree *root)
{
if(root==NULL)
return ;

int min,max,dist;
max=0 ;
min=0 ;
find_MinMax_Vdist(root,&max,&min,0) ;

for(dist=min;dist<=max;dist++)
{
Print_Vertical_Order(root,dist,0) ;
cout<<endl ;
}
}

void find_MinMax_Vdist(tree *root,int *max,int *min,int dist)
{
if(root==NULL)
return ;

if((*min)>dist)
(*min)=dist ;

if((*max)<dist)
(*max)=dist ;

find_MinMax_Vdist(root->left,&(*max),&(*min),dist-1) ;
find_MinMax_Vdist(root->right,&(*max),&(*min),dist+1) ;
}

void Print_Vertical_Order(tree *root,int dist,int curr)
{
if(root==NULL)
return ;

if(curr==dist)
cout<<root->info<<" " ;

Print_Vertical_Order(root->left,dist,curr-1) ;
Print_Vertical_Order(root->right,dist,curr+1) ;
}

---------------------------------------------------------------------------------

PROBLEM :

Given a binary tree, your task is to complete the function verticalOrder which takes one argument the root of the binary tree and prints the node of the binary tree in vertical order .

          1
       /     \
     2       3
   /        /
4       5

The nodes of the above tree printed in vertical order will be
4
2
1 5
3
Your output should be 4 $2 $1 5 $3 $

Note: Each vertical line will be separated by a "$" without quotes.

Input:

The task is to complete the method which takes one argument, root of Binary Tree. There are multiple test cases. For each test case, this method will be called individually.

Output:
The function should print nodes in vertical order where  each vertical line is separated by a "$" without quotes.

Constraints:
1 <=T<= 30
1 <= Number of nodes<= 20


Example:
Input:
2
2
1 2 R 1 3 L
4
10 20 L 10 30 R 20 40 L 20 60 R

Output:
3 $1 $2 $
40 $20 $10 60 $30 $


There are two test cases.  First case represents a tree with 3 nodes and 2 edges where root is 1, left child of 1 is 3 and right child of 1 is 2.   Second test case represents a tree with 4 edges and 5 nodes.

     
--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------

/* A binary tree node has data, pointer to left child
   and a pointer to right child
struct Node
{
    int data;
    struct Node* left;
    struct Node* right;
}; */


/* Should print vertical order such that each vertical line
   is separated by $ */
void find_MinMax_Vdist(Node *,int *,int *,int ) ;
void Print_Vertical_Order(Node *,int ,int ,int*) ;

void verticalOrder(Node *root)
{
    if(root==NULL)
    return ;
 
    int min,max,dist,i;
    max=0 ;
    min=0 ;
    i=0 ;
    find_MinMax_Vdist(root,&max,&min,0) ;

    for(dist=min;dist<=max;dist++)
    {
        i=0 ;
        Print_Vertical_Order(root,dist,0,&i) ;
        cout<<" $" ;
    }
}

void find_MinMax_Vdist(Node *root,int *max,int *min,int dist)
{
 if(root==NULL)
  return ;
 
 if((*min)>dist)
  (*min)=dist ;
 
 if((*max)<dist)
  (*max)=dist ;
 
 find_MinMax_Vdist(root->left,&(*max),&(*min),dist-1) ;
 find_MinMax_Vdist(root->right,&(*max),&(*min),dist+1) ;
}

void Print_Vertical_Order(Node *root,int dist,int curr,int *i)
{
 if(root==NULL)
  return ;
 
 if(curr==dist)
  {
      if((*i)==1)
      cout<<" "<<root->data ;
      else
        {
            cout<<root->data ;
            (*i)=1 ;
        }
  }
 
 Print_Vertical_Order(root->left,dist,curr-1,&(*i)) ;
 Print_Vertical_Order(root->right,dist,curr+1,&(*i)) ;
}

---------------------------------------------------------------------------------