Vertical Order traversal in binary tree

We generally talk about Inorder, PreOrder, PostOrder and LevelOrder traversals in binary tree, but we generally do not use verticalOrder traversal in DSA, let us look into this traversal.

Vertical order traversal is when we traverse the tree level wise and the levels are considered in vertical direction with the mean position being the center or the root TreeNode.

Let us quickly jump into it's algorithm -

This is the tree we are considering -

The Vertical Order Traversal -

Let us see how can we manipulate the results fetched from the vot function for a better clarity -

In this algorithm we keep the distance of root as zero and push the pair of root and distance into a queue. Then we explore the queue's first element, push the left child with a distance one less than the parent's distance and for the right child we push the TreeNode with one more than the parent's distance.

Finally to manipulate the results and show it systematically, by getting the minLevel and maxLevel and iterating over the map where we kept the TreeNodes corresponding to each level.

Finally let us check the result in console -

Happy coding, I keep sharing such content on a regular basis. Do follow me for more such content.