Meta Coding Interview: Tree Column Grouping

The interviewer opens

Hi, and thanks for joining. Welcome to your interview for the software engineer role at Meta. We'll work through one coding problem together, so please think out loud as you go. If you need to step out or take a break, you can use the Pause button at the top right of your screen.

The problem is about laying out a binary tree column by column, and it's in the Problem tab on the right. Please read it through, take your time, and ask me any questions before you start.

The problem

Render a binary tree column by column.

• root: the tree in level order (LeetCode style); null marks a missing child, and an empty list is an empty tree.

The root is in column 0. A left child is one column left of its parent, and a right child is one column right. Return one list per column, with the columns ordered left to right. Within a column, list the values in the order a preorder traversal (node, then its left subtree, then its right subtree) visits them.

Example: root = [1,2,3,null,4,5,null,null,6] → [[2],[1,4,5],[6,3]]

Up to 10^4 nodes.