**By: Saurav**

**2018-01-15 23:20:00 UTC**

Given a binary tree, print a vertical order traversal of it.

Example :

Given binary tree:

6

/ \

3 7

/ \ \

2 5 9

returns

[

[2],

[3],

[6 5],

[7],

[9]

]

At first glance, this problem looks a little intimidating. We have had DFS, BFS, recursion till the leaf, level order etc but how will you deal with a vertical order traversal like the one shown below:

Attempt 1:

The Idea is to use a method of finding the width of the tree by fixing the root at position 0. The length is the leftmost (-ve) index + rightmost index.

So, first, we need to find the maximum width (horizontally) of the tree.

Then, we need to assign a hash map with ranges between leftmost and rightmost indices (inclusive) and allot an array as each value to put the nodes correspondingly.

Finally, we need to traverse the tree in recursion and allot each node to the respective value array. For a given node, its relative value is parent's value - 1 if its left child, or else it parent + 1 if its a right child.

Let's see the code in action:

Running the code with the tests (I took a BST, but we can use a BT as well):

Owned & Maintained by Saurav Prakash

If you like what you see, you can help me cover server costs or buy me a cup of coffee though donation :)