Compute outer boundary of an N-ary tree
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given the root of a rooted **N-ary tree**. Each node contains:
- An integer value.
- An ordered list of children from left to right (0 or more children).
Consider all nodes grouped by their depth (root at depth 0, its children at depth 1, etc.). For each depth `d`:
- Let **L_d** be the *leftmost* node at depth `d` (the first node at that depth when scanning children from left to right).
- Let **R_d** be the *rightmost* node at depth `d` (the last node at that depth when scanning children from left to right).
We define the **outer boundary path** of the tree as the sequence of nodes you would "see" when walking around the outside of the tree, starting from the lowest leftmost node, going up to the root, then going down to the lowest rightmost node:
1. Starting from the **maximum depth D** down to `0`, take `L_D, L_{D-1}, ..., L_0` (bottom-left up to the root).
2. Then from depth `1` up to `D`, take `R_1, R_2, ..., R_D` (top-right down to bottom-right), **skipping** `R_d` when `R_d` is the same node as `L_d` to avoid duplicates on levels with only one node.
Return the list of node values in this exact order.
Assume:
- Total number of nodes `n` satisfies `1 <= n <= 10^5`.
- Tree height `h` can be up to `n` in the worst case.
**Task**: Design an efficient algorithm to compute and return this outer boundary path. Specify the time and space complexity of your approach.
Quick Answer: This question evaluates proficiency in tree data structures and algorithm design, focusing on traversal and boundary extraction in ordered N-ary trees while requiring time and space complexity analysis.
Return boundary values from lowest leftmost node up to root, then down rightmost nodes, skipping duplicates on single-node levels.
Constraints
- Children are ordered left to right
Examples
Input: ({'val': 1, 'children': [{'val': 2, 'children': [{'val': 5}, {'val': 6}]}, {'val': 3}, {'val': 4, 'children': [{'val': 7}]}]},)
Expected Output: [5, 2, 1, 4, 7]
Input: ({'val': 1},)
Expected Output: [1]
Input: ({'val': 1, 'children': [{'val': 2, 'children': [{'val': 3}]}]},)
Expected Output: [3, 2, 1]
Hints
- Level-order traversal gives leftmost and rightmost node per depth.