Vertical Order Tree Traversal | Dataford Interview Questions

How would you implement vertical order traversal of a binary tree?

Implement vertical_order_traversal(root). The input is a nested dictionary tree node with keys val, left, and right; child nodes are dictionaries or null. Return a list of columns ordered from leftmost to rightmost. Within each column, preserve top-to-bottom order, and for nodes at the same position, preserve left-to-right order.

Function Contract

Input: root, a nested dictionary or null
Output: a list of lists containing node values

Constraints

0 <= number of nodes <= 10^4
Node values are integers
Each node has at most one left child and one right child
Columns must be returned from leftmost to rightmost
Nodes in a column must remain top-to-bottom and left-to-right

Function Signature

def vertical_order_traversal(root):

Your question is Vertical Order Tree Traversal. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem