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<>();
			get.add(root.ky);
		}
		else
			get.add(root.ky);


		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))
			get.AddRange(m[hd]);


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


		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: