Compute outer boundary of an N-ary tree

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.

Outer Boundary of an N-ary Tree

Constraints

• Children are ordered left to right

Examples

Example 1

Input: ({'val': 1, 'children': [{'val': 2, 'children': [{'val': 5}, {'val': 6}]}, {'val': 3}, {'val': 4, 'children': [{'val': 7}]}]},)
Output: [5, 2, 1, 4, 7]

Example 2

Input: ({'val': 1},)
Output: [1]

Hints

1. Level-order traversal gives leftmost and rightmost node per depth.