Given a binary tree, the task is to **print it vertically**, see the example below for illustration:

##### Example 1: Print Binary Tree in Vertical Order

Input:

**Output: **

4 2 1,5,6 3,8,9 7

## Solutions

### Method 1: In O(n) using Map

For this solution, we need to group nodes based on their **Horizontal Distances** from the root.

If two nodes have the same Horizontal Distance, then they are on the same vertical line.

Horizontal Distance for root is 0, a right node is considered at +1 horizontal distance and a left edge is considered at -1 horizontal distance.

We can do **level order traversal** of the given Binary Tree, while traversing, we can recursively calculate Horizontal Distance.

Let's pass the initial horizontal distance as 0 for root.

For left subtree, we pass the Horizontal Distance as "Horizontal distance of root" minus 1. For right subtree, we pass the Horizontal Distance as "Horizontal Distance of root" plus 1.

For every "Horizontal Distance" value, we maintain a list of nodes in a tree map.

At the end, print the map **in ascending order of Horizontal Distance** to get "Vertical Order" of the tree.

##### Complexity

**O(n)**and space complexity is

**O(n)**due to auxiliary Map.