Solution: Vertical Order Traversal of a Binary Tree

Statement

Find the vertical order traversal of a binary tree when the root of the binary tree is given. In other words, return the values of the nodes from top to bottom in each column, column by column from left to right. If there is more than one node in the same column and row, return the values from left to right.

Constraints:

• The number of nodes in the tree is in the range [1, 500].
• $0 \leq$ Node.data $\leq 1000$

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

The naive approach would be traversing the tree to get the maximum and minimum horizontal distance of the nodes from the root. Once we have these numbers, we can traverse over the tree again for each distance in the range [maximum, minimum] and return the nodes respectively.

The time complexity of the above algorithm is $O(n^2)$, where $n$ is the number of nodes. The space complexity is $O(n)$.

Optimized approach using tree breadth-first search

Since we’re dealing with a binary tree, the approach that comes to mind is either depth-first search (DFS) or breadth-first search (BFS), which are both viable options. We will select BFS to solve this problem. Using BFS, we can assign the $column − 1$ value to the left child and the $column + 1$ to the right child.

The intuition behind using BFS is that it naturally guarantees that the nodes will be visited level by level. This ensures that the nodes at the top will be visited first, and the nodes at the bottom will be visited last. To traverse the tree from left to right, we need to maintain a hash map that contains the list of all the nodes in a specific column. We’ll denote these columns by their index, where the column of the root will be index 0, the columns on the left side of the root will have a negative index, and the columns on the right side of the root will have a positive index. The index of each column will be a key.

We also need to store the value of the minimum and maximum indexes in two variables so that we can iterate over the indexes to get the nodes in the right order.

Let’s go over the algorithm in detail below:

1. We need to create a hash map called nodeList in which the key will be the index of the column and the value will be the list of nodes in that column.

2. We initialize two variables to store the minimum and maximum values of the index.

3. During BFS, we also maintain a queue to keep track of the order of nodes that need to be visited. We’ll initialize the queue by adding the root to it along with the column index of the root, which is 0.

4. Next, we carry out BFS using a loop until the queue is empty. We iterate over the queue elements and pop them. The values in the queue consist of a node and the index of the column.

5. If the queue contains a node that is not NULL, we add the value of the node to nodeList along with the index of the column. We also keep updating the minimum and maximum values of the index. Then, we append the children of this node to the queue with their index values. The left child has an index value of the current index $- 1$, and the right child has a value of the current index $+ 1$.

6. At the end of all the iterations, the nodeList hash map contains the values of all the nodes in all the columns, but the values of each column are not in the correct order.

7. We’ll iterate over the index range using the variables that stored the minimum and maximum indexes. Finally, we return the values of the nodes in the correct order.