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$

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.

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)$.

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$ ...