Binary Tree in Vertical Order

http://www.geeksforgeeks.org/print-binary-tree-vertical-order-set-2/

Given a binary tree, print it vertically. The following example illustrates vertical order traversal.

1 / \ 2 3 / \ / \ 4 5 6 7 \ \ 8 9 The output of print this tree vertically will be: 4 2 1 5 6 3 8 7 9

1. Do the level order traversal

2. keep adding each node in hash-table with linked-list

3. At the end print hash table in order.

Node Value (Horizontal distance, Vertical Distance)

1 (0,0)

2 (1,1)

3 (1,1)

4 (-2,2)

5 (0,2)

6 (0,2)

7 (2,2)

8 (1,3)

9 (3.3)

Hash Table

-2 : 4

-1 : 2

0 : 1, 5, 6

1 : 3, 8

2 : 7

3 : 9

Time Complexity of hashing based solution can be considered as O(n) under the assumption that we have good hashing function that allows insertion and retrieval operations in O(1) time. In the C++ implementation, map of STL is used. map in STL is typically implemented using a Self-Balancing Binary Search Tree where all operations take O(Logn) time.