In this problem, we have given a pointer denoting the root of the binary tree and your task is to print the binary tree in the vertical order.
Table of Contents
Example
Input
1
/ \
2 3
/ \ / \
4 5 6 7
\ \
8 9Output
4
2
1 5 6
3 8
7
9
Explanation
Algorithm for print a Binary Tree in Vertical Order
- Insert the elements at the different nodes.
- Set distance to 0.
- Check if the root is equal to null if true then return.
- Set keyValue to the value of distance as a key in the map.
- Check if “keyValue” is equal to null.
- If true, then initialize a “keyValue” to a new vector and add root value(element) in that vector.
- Else, add root value in that vector because is already existing.
- Check if “keyValue” is equal to null.
- Put the distance and “keyvalue” on the map.
- Recursively calls printVerticalTree function with “root.left”, distance -1, “m” and “root.right”, distance +1, “m” for left and right subtrees respectively.
- Print map.
Explanation for print a Binary Tree in Vertical Order
Our main idea for printing the Binary Tree in a vertical order is to recursively call the functions with the updated values passing every time as an argument and keep updating our map according to the output we want.
Starting with the insertion of nodes at root, root.right, root.left, root.left.left, and so on, we have our values as our input. We need to take these inputs one by one, starting with the leftmost element in the tree. We initialize a vector which is then inserted into the map with an integer as a key for each index of the vector. In a vector, we are going to store all the values vertically and then put distances and keyValue in the map as a “keyvalue” pair.
Main Part
When we first pass the root, it is not having a null value. Then map.get(distance) will store in the keyValue, if then keyValue is found to be null means as a ‘distance’ as key in the map it is not having any value, then we initialize a vector keyValue and add the root.key which means some element at the which the root.key is indicating. If keyValue is not null it means there is already some existing values that are stored along it’s ‘key’. We just need to add that “root.key”(the element which is being indicated).
In all of this, there is one more important term which is distance. Distance means the vertical distance of any node in the tree from the root node, we get numbers as a distance, as a left subtree we get negative numbers and for the right subtrees we get positive numbers and for the right and nodes below of the root is considered to at 0 distance from the root, which we pass as our arguments recursively. Every time we pass distance as an argument, it means we are going to store some values along with it which is turned out to be a key in a map, like for this example, -2, -1, 0, 1, 2, 3. These are the keys for each vector in which we are going to store our elements.
We need to print the values from the map, all the values in the map have keys (sorted) starting from the leftmost element means -2 to 3 which means rightmost element. We will get all the elements vertically and print it.
Implementation for print a Binary Tree in Vertical Order
C++ Program
#include <iostream>
#include <vector>
#include <map>
using namespace std;
struct Node
{
int key;
Node *left, *right;
};
struct Node* newNode(int key)
{
struct Node* node = new Node;
node->key = key;
node->left = node->right = NULL;
return node;
}
void printVerticalTree(Node* root, int distance, map<int, vector<int>> &mymap)
{
if (root == NULL)
return;
mymap[distance].push_back(root->key);
printVerticalTree(root->left, distance-1, mymap);
printVerticalTree(root->right, distance+1, mymap);
}
void printVerticalOrder(Node* root)
{
map < int,vector<int> > mymap;
int distance = 0;
printVerticalTree(root, distance,mymap);
map< int,vector<int> > :: iterator it;
for (it=mymap.begin(); it!=mymap.end(); it++)
{
for (int i=0; i<it->second.size(); ++i)
cout << it->second[i] << " ";
cout << endl;
}
}
int main()
{
Node *root = newNode(3);
root->left = newNode(4);
root->right = newNode(6);
root->left->left = newNode(8);
root->left->right = newNode(11);
root->right->left = newNode(14);
root->right->right = newNode(17);
root->right->left->right = newNode(18);
root->right->right->right = newNode(25);
cout << "Vertical order traversal is \n";
printVerticalOrder(root);
return 0;
}
Vertical order traversal is 8 4 3 11 14 6 18 17 25
Java Program
import java.util.TreeMap;
import java.util.Vector;
import java.util.Map.Entry;
class printBinarytreeVertical
{
static class Node
{
int key;
Node left;
Node right;
Node(int data)
{
key = data;
left = null;
right = null;
}
}
static void printVerticalTree(Node root, int distance, TreeMap<Integer,Vector<Integer>> map)
{
if(root == null)
{
return;
}
Vector<Integer> keyValue = map.get(distance);
if(keyValue == null)
{
keyValue = new Vector<>();
keyValue.add(root.key);
}
else
keyValue.add(root.key);
map.put(distance, keyValue);
printVerticalTree(root.left, distance-1, map);
printVerticalTree(root.right, distance+1, map);
}
static void printVerticalOrder(Node root)
{
TreeMap<Integer,Vector<Integer>> m = new TreeMap<>();
int distance =0;
printVerticalTree(root,distance,m);
for (Entry<Integer, Vector<Integer>> getentry : m.entrySet())
{
System.out.println(getentry.getValue());
}
}
public static void main(String[] args)
{
Node root = new Node(3);
root.left = new Node(4);
root.right = new Node(6);
root.left.left = new Node(8);
root.left.right = new Node(11);
root.right.left = new Node(14);
root.right.right = new Node(17);
root.right.left.right = new Node(18);
root.right.right.right = new Node(25);
System.out.println("Vertical Order traversal is");
printVerticalOrder(root);
}
}
Vertical Order traversal is [8] [4] [3, 11, 14] [6, 18] [17] [25]
Complexity Analysis for print a Binary Tree in Vertical Order
Time Complexity
O(n Logn) where “n” is the number of elements in a tree.
Space Complexity
O(n) where “n” is the number of elements in a tree.