Linked List and Tree Traversal | Dataford Interview Questions

Groupon can represent a simplified deal-category hierarchy as a binary tree, where each node contains a category value and up to two child categories. Given the root category, return the categories in level-order from top to bottom, reading each level from left to right.

Formal Specification

Implement level_order_categories(root). The input root is either None or a nested dictionary with this form: {"value": value, "left": node_or_none, "right": node_or_none}. The value can be an integer or string. Return a list of lists, where each inner list contains the values found at one tree depth.

Do not modify the tree.

Constraints

0 <= number of nodes <= 10^4
Tree height is at most 10^4
Each node has at most two children
Node values are strings or integers

Function Signature

def level_order_categories(root):

Your question is Linked List and 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