Here is the interview question prompt, presented for reference.
In a binary tree, each node has a position defined by its (row, col)
coordinates. The vertical order traversal
is a method of visiting all the nodes in the tree column-by-column, starting from the leftmost to the rightmost columns. In this traversal, for each column, you will go from the top node to the bottom node.
Imagine the tree as a grid. The root node sits at (0, 0)
and as you move down the tree, the row number increases. When you go left, the column number decreases, and when you go right, the column number increases.
Sometimes, you'll find multiple nodes in the same row and column. When this happens, you should sort these nodes based on their values, in ascending order.
For any node at (row, col)
, its children will be positioned as follows:
- The left child will be at (row + 1, col - 1)
- The right child will be at (row + 1, col + 1)
[0, 1000]
You can see the full challenge with visuals at this link.
Challenges • Asked almost 2 years ago by Jake from AlgoDaily
This is the main discussion thread generated for Nodes in Binary Tree Columns (Main Thread).