987. Vertical Traversal

BFS Is Still Very Important

Although not used as frequently or famously as DFS, which is closely tied with recursion,

BFS still has its own dominance in level-order traversals on trees and graphs.

Should never allow yourself to know only one of these two search algorithms.

If you aren't familiar enough with BFS yet, take a look at this GeeksforGeeks article first: https://www.geeksforgeeks.org/dsa/breadth-first-search-or-bfs-for-a-graph/

After understanding the basics of BFS, come back to solve Problem 987.

Vertical Order Traversal of a Binary Tree

Although this is a Hard problem, I would still say:

Problem 987 is an excellent warm-up for BFS. 😉😏

Row & Column Coordinates of a Binary Tree

The problem states that if a parent node is located at $(x, y)$,

its left and right children are located at $(x + 1, y - 1)$ and $(x + 1, y + 1)$, respectively.

This is very straightforward:

• Moving to left child means moving down-left, so row increases by 1 while column decreases by 1.

• Moving to right child means moving down-right, so row also increases by 1, but this time column increases by 1 as well.

Naturally, root node starts at $(0, 0)$, since root stands right in the middle.

Node Ordering Rule: Sort by Column First, Then by Value Within Same Column

Track Each Column Separately

This is required by the problem itself and also follows naturally from properties of a binary tree.

Whenever we move down one level, the tree may continue expanding toward the left.

Whether it also expands toward the right depends on actual tree structure.

This makes BFS, which explores tree level by level, a suitable approach for this problem.

We first prepare an array called columnsValues.

From left to right, it stores an exclusive array for every column in binary tree.

Each exclusive array stores all node values of that column in sorted order.

Key is Simply This

While performing BFS, we need to track:

Which column does the leftmost array currently stored in columnsValues represent?

And which column does the rightmost array currently represent?

Whenever BFS reaches a node whose column is further left than leftmostCol,

columnsValues must insert an empty array at left front.

This empty array stores node values of new leftmost column.

Conversely, if the node lies further right than rightmostCol,

columnsValues must append an empty array to back right.

This empty array stores node values of new rightmost column.

Able to Expand in Both Directions

Now we know that columnsValues must support insertion at both left and right.

The answer apparently becomes deque: a perfect foundation for columnsValues.

Locating Index in columnsValues After Expansion

Some of you may wonder:

If columnsValues can expand toward left, how can we still locate correct position for a node using an index?

Pause here for a moment and think about it before reading on. ~~

Already Right Before Your Eyes

That's right—leftmostCol is the key.

Since leftmostCol stores column index represented by leftmost array in columnsValues,

subtracting leftmostCol from any current column value

automatically gives correct index inside columnsValues. 🤓😎

After Collecting All Columns and Nodes

Don't forget that node values inside each column still need to be sorted in ascending order.

Once every column has been sorted internally, simply return result, since columns themselves have already been arranged from left to right.

C++

#include <queue>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode()
        : val(0)
        , left(nullptr)
        , right(nullptr) {}

    TreeNode(int x)
        : val(x)
        , left(nullptr)
        , right(nullptr) {}

    TreeNode(int x, TreeNode* left, TreeNode* right)
        : val(x)
        , left(left)
        , right(right) {}
};

vector<vector<int>> findVerticalTraversal(TreeNode* root) {
    // Each tuple format: {tree node, row, column}.
    deque<tuple<TreeNode*, int, int>> queue = {{root, 0, 0}};

    // Each tuple format: {row, value}.
    deque<vector<tuple<int, int>>> columnsValues = {{}};

    int leftmostCol = 0, rightmostCol = 0;

    while (!queue.empty()) {
        auto [node, row, column] = queue.front();
        queue.pop_front();

        if (column < leftmostCol) {
            leftmostCol = column;
            columnsValues.push_front({});
        }

        if (column > rightmostCol) {
            rightmostCol = column;
            columnsValues.push_back({});
        }

        columnsValues[column - leftmostCol].push_back({row, node->val});

        if (node->left != nullptr)
            queue.push_back({node->left, row + 1, column - 1});

        if (node->right != nullptr)
            queue.push_back({node->right, row + 1, column + 1});
    }

    vector<vector<int>> verticalTraversal = {};

    for (auto columnValues : columnsValues) { // Need to sort so no const.
        verticalTraversal.push_back({});

        sort(columnValues.begin(), columnValues.end());
        for (const auto& [row, value] : columnValues)
            verticalTraversal.back().push_back(value);
    }

    return verticalTraversal;
}

Python

from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None) -> None:
        self.val = val
        self.left = left
        self.right = right


def find_vertical_traversal(root: TreeNode) -> list[list[int]]:
    # Each tuple format: (tree node, row, column).
    queue: deque[tuple[TreeNode, int, int]] = deque([(root, 0, 0)])

    # Each tuple format: (row, value).
    columns_values: deque[list[tuple[int, int]]] = deque([[]])

    leftmost_col, rightmost_col = 0, 0

    while queue:
        node, row, column = queue.popleft()

        if column < leftmost_col:
            leftmost_col = column
            columns_values.appendleft([])

        if column > rightmost_col:
            rightmost_col = column
            columns_values.append([])

        columns_values[column - leftmost_col].append((row, node.val))

        if node.left:
            queue.append((node.left, row + 1, column - 1))
        if node.right:
            queue.append((node.right, row + 1, column + 1))

    vertical_traversal: list[list[int]] = []

    for column_values in columns_values:
        vertical_traversal.append([])

        column_values.sort()
        for _, value in column_values:
            vertical_traversal[-1].append(value)

    return vertical_traversal

Space complexity is $O(n)$, where $n$ is number of nodes in binary tree.

This naturally comes from FIFO queue used by BFS.

Time complexity is $O(n \log n)$ due to sorting.