Vertical Order Traversal of Binary Tree

Problem: Given a binary tree, print it vertically. Look at the below image to understand it better

(Image taken from geeksforgeeks)

Example:

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

Approach: We can use horizontal distances of the node to see what all the nodes are in same vertical line or not. We can define horizontal distance as follows:

1. Horizontal distance of root is 0.
2. if a node's horizontal distance is n then horizontal distance of node's left and right will be n - 1 and n + 1 respectively.

We can maintain a hash with key as horizontal distance and value as list of nodes. We will do a level order traversal fill the hash with horizontal distance and nodes. In the end we will just print all the values of hash in key's sorted order.

Note that we could use Pre Order traversal too instead of level order traversal but it could result in incorrect order of nodes at a particular horizontal distance. If you look at the example given in the problem, you will observe with pre-order traversal 12 will come before 10 which is not right.

Implementation in C#:

        public List<List<int>> VerticalOrderTraversal()

        {

            if (this.Root == null)

            {

                return new List<List<int>>();

            }

            int hd = 0;

            Queue<Tuple<BinaryTreeNode, int>> queue = new Queue<Tuple<BinaryTreeNode, int>>();

            queue.Enqueue(new Tuple<BinaryTreeNode, int>(this.Root, hd));

            SortedDictionary<int, List<int>> hash = new SortedDictionary<int, List<int>>();

            while(queue.Count > 0)

            {

                Tuple<BinaryTreeNode, int> tuple = queue.Dequeue();

                BinaryTreeNode node = tuple.Item1;

                hd = tuple.Item2;

                if (!hash.ContainsKey(hd))

                {

                    hash.Add(hd, new List<int>());

                }

                hash[hd].Add(node.Value);

                if (node.LeftNode != null)

                {

                    queue.Enqueue(new Tuple<BinaryTreeNode, int>(node.LeftNode, hd - 1));

                }

                if (node.RightNode != null)

                {

                    queue.Enqueue(new Tuple<BinaryTreeNode, int>(node.RightNode, hd + 1));

                }

            }

            List<List<int>> result = new List<List<int>>();

            foreach (int key in hash.Keys)

            {

                result.Add(hash[key]);

            }

            return result;

        }

Complexity: O(n)