Column Traversal of a Binary Tree | Dataford Interview Questions

Given a binary tree (not BST), print the column traversal from leftmost to rightmost column, top node first within a column. Asked in the onsite coding stage. from 7335359

Represent each node as { "val": number, "left": node|null, "right": node|null }. Implement def vertical_order(root):, returning a list of columns, where each column is a list of node values. Group nodes by horizontal distance from the root, with left child at distance -1 and right child at distance +1. Use breadth-first traversal so nodes appear top to bottom.

Example: 1 with left 2 and right 3 returns [[2], [1], [3]]. An empty tree returns [].

Constraints

The tree contains 0 to 10^5 nodes.
Each node value is an integer.
The input is a valid binary tree represented by nested node dictionaries.
A node has keys val, left, and right.

Function Signature

def vertical_order(root):

Your question is Column Traversal of a Binary Tree. 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

Given a binary tree (not BST), print the column traversal from leftmost to rightmost column, top node first within a column. Asked in the onsite coding stage. from 7335359

Example: 1 with left 2 and right 3 returns [[2], [1], [3]]. An empty tree returns [].

Constraints

The tree contains 0 to 10^5 nodes.
Each node value is an integer.
The input is a valid binary tree represented by nested node dictionaries.
A node has keys val, left, and right.

Function Signature

def vertical_order(root):

Your question is Column Traversal of a Binary Tree. 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.