Vertical Order Traversal of a Binary Tree - Video Solutions

Problem Overview: You are given the root of a binary tree and need to return its vertical order traversal. Each node is assigned coordinates: the root starts at column 0, left child moves to col - 1, and right child moves to col + 1. Nodes must be grouped by column from left to right. If multiple nodes share the same row and column, they must be ordered by their values.

Approach 1: BFS with Coordinate Tracking (Time: O(n log n), Space: O(n))

This approach performs a level-order traversal using a queue while tracking each node’s (row, column) coordinates. Start with the root at (0,0). When visiting a node, push its children into the queue with updated coordinates: left child (row+1, col-1) and right child (row+1, col+1). Store nodes in a hash map where the key is the column and the value is a list of (row, value) pairs. After traversal, sort each column’s entries first by row and then by value to satisfy the ordering constraint. Finally, iterate columns from the minimum to maximum index to build the result. This method is intuitive because Breadth-First Search naturally processes nodes level by level, making row tracking straightforward.

Approach 2: DFS with Sorting (Time: O(n log n), Space: O(n))

This solution uses recursive traversal to record the position of every node. During the DFS, pass the current row and column values to children and store tuples (column, row, value) in a list. After visiting all nodes, sort the list primarily by column, then by row, and finally by node value. Once sorted, iterate through the list and group nodes with the same column together. The advantage of this approach is its simplicity: all ordering logic is handled by a single sort operation. It combines Depth-First Search traversal with a sorting step to enforce the problem’s ordering rules.

Recommended for interviews: BFS with coordinate tracking is usually easier to reason about during interviews because it mirrors the grid-like interpretation of the tree. You explicitly track positions and group nodes by column using a hash table. DFS with sorting is equally valid and often shorter to implement, but interviewers typically expect you to explain how row and column ordering are preserved. Showing the coordinate idea first demonstrates strong problem modeling, while the optimized grouping and sorting show implementation skill.