Uber·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Uber SWE interview with a tree traversal problem that sounds manageable until you actually sit down and think through all the edge cases. Not the worst coding round I've had but definitely not a gimme.

Questions Asked (1)

Given the root of a binary tree, return the vertical order traversal as a list of lists. Each node has a (row, col) position, children shift one column left or right, and ties within the same row and column are broken by node value.

Algorithms & Data Structures

Author's notes

I got the basic structure down pretty quick, grouping nodes by column using a map.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a BFS traversal to assign (row, col) coordinates to each node, then group nodes by column and sort within each column by row and value. Alternatively, use a DFS with a TreeMap keyed by column, storing lists of (row, value) and sorting each list. Return the columns in ascending order.

Pro tip: Clarify the tie-breaking rule: if two nodes have the same row and column, order by node value. Also, mention that BFS naturally processes nodes in row order, simplifying sorting.

1. Clarify the problem

Confirm the coordinate system: root at (0,0), left child at (row+1, col-1), right child at (row+1, col+1). Ask about tie-breaking: if same row and column, sort by node value.

2. Choose traversal and data structure

Use BFS with a queue to process nodes level by level, or DFS with a map. Use a TreeMap to group nodes by column, ensuring columns are sorted.

3. Collect nodes with coordinates

During traversal, for each node, record its row, column, and value. Store in a list associated with its column in the map.

4. Sort within each column

For each column, sort the list of nodes by row ascending, then by value ascending. This handles tie-breaking.

5. Return result

Extract the sorted lists from the TreeMap in column order and return as a list of lists.

Key Points to Mention

BFS ensures nodes are processed in row order, so within a column, nodes are already sorted by row if we append in BFS order; then only need to sort by value for ties.
Using a TreeMap automatically keeps columns sorted, avoiding a separate sort of column keys.
Time complexity: O(N log N) due to sorting within columns; space complexity: O(N) for the map and queue.
Edge cases: empty tree, single node, skewed tree, nodes with same row and column (tie-breaking by value).
Alternative: DFS with a map, but need to sort by row and value explicitly.
Mention that the problem is similar to LeetCode 987 (Vertical Order Traversal of a Binary Tree).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.