Vertical Order Traversal of a Binary Tree

ALSO CHECK: Algorithms and System Design Interview Questions

Let's say we have below Binary Tree

In vertical traversal, we print nodes of a binary tree in vertical order by assuming that the left and right child of a node makes 45 degree angle with the parent.

We need to check the Horizontal Distances from the root for all nodes. If two nodes have the same Horizontal Distance (HD), then they are on the same vertical line.

FYI, HD for root is 0, a right edge (edge connecting to right subtree) is considered as +1 horizontal distance and a left edge is considered as -1 horizontal distance.

In short,

• Horizontal Distance for root=0
• Horizontal Distance for left child=Horizontal Distance of Parent-1
• Horizontal Distance for right child=Horizontal Distance of Parent +1

The nodes with the same HD comes in a horizontal line, e.g: b & i. Also a, e/f are in a horizontal line, here both e and f have same levels, so both can be considered as one.

ALSO CHECK: Binary Search Trees, Balance Search Trees, 2-3 ST, Red- Black BST

Algorithm For Vertical Order Traversal of a Binary tree
1). Enqueue the root.
2). Update the HD for root as 0.
3). Create a Hash Table. Add HD=0 in the hashtable, with value as root.
4). In the while loop, started dequeue the queue. Do it till the queue is empty.
5). In each iteration, check left and right node, calculate the HD and update the HD in Hash table. After this enqueue the left and right child.
6). The HashTable contain the HD and list of nodes (with the same HD).



-K Himaanshu Shuklaa..