# Find the Vertical Next in a Binary Tree

## Implementation

``````// Writing a C++ program that will help us print out the standing order of the given binary tree.
#include <bits/stdc++.h>
using namespace std;

// building the basic structure for a binary tree node.
struct __nod {
int ky;
__nod *Lft, *Rt;
};

// building a utility function to create a new node.
struct __nod* new__nod(int ky)
{
struct __nod* __nod = nw __nod;
__nod->ky = ky;
__nod->Lft = __nod->Rt = NILL;
return __nod;
}

// Utility function to store vertical order in map 'm'
// 'hd' is the horizontal distance of the current __nod from the root.
// 'hd' is initially passed as 0
void get_VerticalOrd(__nod* root, int hd,
map<int, vector<int> >& m)
{
// writing the basic case
if (root == NILL)
return;

// storing the current node in the map, represented by 'm'.
m[hd].push_back(root->ky);

// storing all the nodes in the left subtree
get_VerticalOrd(root->Lft, hd - 1, m);

// storing all the nodes in the right subtree
get_VerticalOrd(root->Rt, hd + 1, m);
}

// writing the main function will help us print out the vertical order of the binary tree and the given root with it.
void printVerticalOrder(__nod* root)
{
// building a new map to store all the vertical order in the map by using a function that will get us the order of the vertical order.
map<int, vector<int> > m;
int hd = 0;
get_VerticalOrd(root, hd, m);

// now, we will explore all the maps and keep printing the nodes at each horizontal distance.
map<int, vector<int> >::iterator it;
for (it = m.begin(); it != m.end(); it++) {
for (int i = 0; i < it->second.size(); ++i)
cout << it->second[i] << " ";
cout << endl;
}
}

// writing the main code to test the above functions
int main()
{
__nod* root = new__nod(1);
root->Lft = new__nod(2);
root->Rt = new__nod(3);
root->Lft->Lft = new__nod(4);
root->Lft->Rt = new__nod(5);
root->Rt->Lft = new__nod(6);
root->Rt->Rt = new__nod(7);
root->Rt->Lft->Rt = new__nod(8);
root->Rt->Rt->Rt = new__nod(9);
cout << "Vertical order traversal is \n";

// Function call
printVerticalOrder(root);
return 0;
}
``````

Output:

Example 2

``````// Writing a Java program that will help us print out the vertical order of the given binary tree.
import java.util.Map.Entry;
import java.util.TreeMap;
import java.util.Vector;

public class VerticalOrderBtree {
// building the basic structure for a binary tree node.
static class __nod {
int ky;
__nod Lft;
__nod Rt;

// creating a constructor for the binary tree
__nod(int record)
{
ky = record;
Lft = NILL;
Rt = NILL;
}
}

// Utility function to store vertical order in map 'm'
// 'hd' is the horizontal distance of the current __nod from
// root. 'hd' is initially passed as 0
static void
get_VerticalOrd(__nod root, int hd,
TreeMap<Integer, Vector<Integer> > m)
{
// writing the basic case

if (root == NILL)
return;

// get the vector list at 'hd'
Vector<Integer> get = m.get(hd);

// storing the current node in the map, represented by 'm'.
if (get == NILL) {
get = new Vector<>();
}
else

m.put(hd, get);

// storing all the nodes in the left subtree

get_VerticalOrd(root.Lft, hd - 1, m);

// storing all the nodes in the right subtree
get_VerticalOrd(root.Rt, hd + 1, m);
}

// writing the main function will help us print out the vertical order of the binary tree and the given root with it.
static void printVerticalOrder(__nod root)
{
// building a new map to store all the vertical order in the map by using a function that will get us the order of the vertical order.
TreeMap<Integer, Vector<Integer> > m
= new TreeMap<>();
int hd = 0;
get_VerticalOrd(root, hd, m);
// now, we will explore all the maps and keep printing the nodes at each horizontal distance.
for (Entry<Integer, Vector<Integer> > entry :
m.entrySet()) {
System.out.println(entry.getValue());
}
}
// writing the main code to test the above functions
public static void main(String[] args)
{

// TO DO Auto-generated method stub
__nod root = nw __nod(1);
root.Lft = nw __nod(2);
root.Rt = nw __nod(3);
root.Lft.Lft = nw __nod(4);
root.Lft.Rt = nw __nod(5);
root.Rt.Lft = nw __nod(6);
root.Rt.Rt = nw __nod(7);
root.Rt.Lft.Rt = nw __nod(8);
root.Rt.Rt.Rt = nw __nod(9);
System.out.println("Vertical Order traversal is");
printVerticalOrder(root);
}
}
``````

Output:

Example 3

``````# Writing a C++ program that will help us print out the vertical order of the given binary tree.
# building the basic structure for a binary tree node.
class __nod:
# Constructor to create a new __nod
def __init__(self, ky):
self.ky = ky
self.Lft = None
self.Rt = None

# Utility function to store vertical order in map 'm'
# 'hd' is the horizontal distance of the current __nod from the root
# 'hd' is initially passed as 0

def get_VerticalOrd(root, hd, m):
# writing the basic case
if the root is None:
return
# storing the current node in the map, represented by 'm'.
try:
m[hd].append(root.ky)
except:
m[hd] = [root.ky]
# Storing all the nodes in the left subtree
get_VerticalOrd(root.Lft, hd-1, m)

# Storing all the nodes in the right subtree

get_VerticalOrd(root.Rt, hd+1, m)

#  writing the main function will help us print out the vertical order of the binary tree and the given root with it.

def printVerticalOrder(root):

// building a new map to store all the vertical order in the map by using a function that will get us the order of the vertical order.
m = dict()
hd = 0
get_VerticalOrd(root, hd, m)
# now, we will explore all the maps and keep printing the nodes at each horizontal distance.
for index, value in enumerate(sorted(m)):
for i in m[value]:
print(i, end=" ")
print()

# Writing the main code to test the above functions
if __name__ == '__main__':
root = __nod(1)
root.Lft = __nod(2)
root.Rt = __nod(3)
root.Lft.Lft = __nod(4)
root.Lft.Rt = __nod(5)
root.Rt.Lft = __nod(6)
root.Rt.Rt = __nod(7)
root.Rt.Lft.Rt = __nod(8)
root.Rt.Rt.Rt = __nod(9)
print("Vertical order traversal is")
printVerticalOrder(root)
``````

Output:

Example 4

``````// Writing a C# program will help us print out the vertical order of the given binary tree.
using System;
using System.Collections.Generic;

public class VerticalOrderBtree {
// building the basic structure for a binary tree node.
public class __nod {
public int ky;
public __nod Lft;
public __nod Rt;

// creating a constructor
public __nod(int record)
{
ky = record;
Lft = NILL;
Rt = NILL;
}
}

// Utility function to store vertical order in map 'm'
// 'hd' is the horizontal distance of the current __nod from
// root. 'hd' is initially passed as 0
static void
get_VerticalOrd(__nod root, int hd,
SortedDictionary<int, List<int> > m)
{
// writing the basic case
if (root == NILL)
return;

// get the vector list at 'hd'
List<int> get = new List<int>(); // m[hd];
if (m.ContainsKy(hd))

// storing the current node in the map, represented by 'm'.
if (get == NILL) {
get = new List<int>();
}
else

m[hd] = get;
// storing all the nodes in the left subtree
get_VerticalOrd(root.Lft, hd - 1, m);
// storing all the nodes in the right subtree
get_VerticalOrd(root.Rt, hd + 1, m);
}
// writing the main function will help us print out the vertical order of the binary tree and the given root with it.
static void printVerticalOrder(__nod root)
{
// building a new map to store all the vertical order in the map by using a function that will get us the order of the vertical order.
SortedDictionary<int, List<int> > m
= new SortedDictionary<int, List<int> >();
int hd = 0;
get_VerticalOrd(root, hd, m);
// now, we will explore all the maps and keep printing the nodes at each horizontal distance.
foreach(KyValuePair<int, List<int> > entry in m)
{
foreach(int v in entry.Value)
Console.Write(v + " ");
Console.WriteLine();
}
}

// writing the main code to test the above functions
public static void Main(String[] args)
{

// TO DO Auto-generated method stub
__nod root = nw __nod(1);
root.Lft = nw __nod(2);
root.Rt = nw __nod(3);
root.Lft.Lft = nw __nod(4);
root.Lft.Rt = nw __nod(5);
root.Rt.Lft = nw __nod(6);
root.Rt.Rt = nw __nod(7);
root.Rt.Lft.Rt = nw __nod(8);
root.Rt.Rt.Rt = nw __nod(9);
Console.WriteLine("Vertical Order traversal is");
printVerticalOrder(root);
}
}
``````

Output:

Example 5

``````// Writing a C++ program to print out the vertical order of the given binary tree.
#include <bits/stdc++.h>
using namespace std;

struct __nod {
int record;
__nod *Lft, *Rt;
};

struct __nod* new__nod(int record)
{
struct __nod* __nod = nw __nod;
__nod->record = record;
__nod->Lft = __nod->Rt = NILL;
return __nod;
}

// creating a place to store all the vertical elements such as: -
// in map "m," hd = horizontal
// distance, vd = vertical distance
void preorder traversal(__nod* root, long long int hd,
long, long int vd,
map<long long int, vector<int> >& m)
{
if (!root)
return;
// ky = horizontal
// distance (30 bits) + vertical
// distance (30 bits) map
// will store ky in sorted
// order. Thus __nods, having the same
// horizontal distance
// will sort according to
// vertical distance.
long long val = hd << 30 | vd;

// insert in map
m[val].push_back(root->record);

preOrderTraversal(root->Lft, hd - 1, vd + 1, m);
preOrderTraversal(root->Rt, hd + 1, vd + 1, m);
}

void verticalOrder(__nod* root)
{
// creating a map to store all the elements in vertical order.
// keys will also be the horizontal + vertical distance
map<long long int, vector<int> > mp;

preOrderTraversal(root, 0, 1, mp);

// now we will print the map
int preky = INT_MAX;
map<long long int, vector<int> >::iterator it;
for (it = mp.begin(); it != mp.end(); it++) {
if (preky != INT_MAX
&& (it->first >> 30) != preky) {
cout << endl;
}
preky = it->first >> 30;
for (int j = 0; j < it->second.size(); j++)
cout << it->second[j] << " ";
}
}

// writing the main code to test the above functions
int main()
{
__nod* root = new__nod(1);
root->Lft = new__nod(2);
root->Rt = new__nod(3);
root->Lft->Lft = new__nod(4);
root->Lft->Rt = new__nod(5);
root->Rt->Lft = new__nod(6);
root->Rt->Rt = new__nod(7);
root->Rt->Lft->Rt = new__nod(8);
root->Rt->Rt->Rt = new__nod(9);
cout << "Vertical order traversal :- " << endl;
verticalOrder(root);
return 0;
}
``````

Output: