DSA interview question

Vertical Order Traversal of a Binary Tree

Medium · Data structures · Topics: tree, dfs, bfs, hash map

The problem

A tree-visualisation tool draws a binary tree on a grid: the root at column 0 and row 0, a left child at (row + 1, col − 1), a right child at (row + 1, col + 1). It then lists the nodes column by column from left to right, top to bottom inside each column. Nodes that land in the same row and column are listed in increasing value. Record (col, row, value) for every node with a traversal, sort, and group by column.

Example: [3, 9, 20, null, null, 15, 7] → [[9], [3, 15], [20], [7]].

Function signature

vector<vector<int>> verticalTraversal(TreeNode* root);

Test cases

Input (level order)	Output	Explanation
`[3, 9, 20, null, null, 15, 7]`	`[[9], [3, 15], [20], [7]]`	3 and 15 share column 0
`[1, 2, 3, 4, 5, 6, 7]`	`[[4], [2], [1, 5, 6], [3], [7]]`	5 and 6 share row 2, column 0
`[1, 2, 3, 4, 6, 5, 7]`	`[[4], [2], [1, 5, 6], [3], [7]]`	The same position is sorted by value
`[1]`	`[[1]]`
`[]`	`[]`

(Confirm: order by column, then row, then value; this is LeetCode 987's rule, and GeeksforGeeks' version keeps level order for ties instead.)

How interviewers phrase it

"Calculate the vertical order traversal of the binary tree" (LeetCode 987).

Clarifying questions to ask

How should nodes at the same row and column be ordered? (By value here; some versions use left-to-right level order.)
Is the root at column 0? (Yes: left is −1, right is +1.)
Can values repeat? (Yes.)

Follow-ups to expect

"Which data structure?"
"BFS or DFS?"
"How is this related to top and bottom views?"
"Can you avoid the log factor?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview