Collect a Binary Tree's Outer Boundary Values Anticlockwise

The question asks for the boundary of a binary tree and its sum. Return the boundary values in boundary order, read anticlockwise from the root; the boundary sum is the total of the returned list.

Function Signature

def tree_boundary(values: list[int], left: list[int], right: list[int]) -> list[int]:

Rules

• The tree has n nodes numbered 0 to n - 1, and node 0 is the root. values[i] is the value of node i, and left[i] and right[i] are the indices of its left and right children, or -1 when that child is missing.
• A leaf is a node with no children. The root is never treated as a leaf, even when it has no children.
• The left boundary starts at the root's left child. From there, repeatedly move to the current node's left child if it exists, otherwise to its right child, and stop at the first leaf. The left boundary is the nodes visited, excluding that final leaf. If the root has no left child, the left boundary is empty.
• The right boundary is the mirror image: start at the root's right child, repeatedly move to the right child if it exists, otherwise to the left child, stop at the first leaf and exclude it. If the root has no right child, the right boundary is empty.
• The leaves are all the leaves of the tree, in the order a left-to-right depth-first traversal reaches them.
• Return the root's value, then the left boundary's values from top to bottom, then the leaves' values, then the right boundary's values from bottom to top.

Constraints

• 1 <= n <= 10^4, and len(values) == len(left) == len(right) == n
• -1000 <= values[i] <= 1000
• Every child index is -1 or between 1 and n - 1, every node other than 0 is the child of exactly one node, and the links form a single binary tree rooted at node 0.
• The tree can be a single path, so its depth can reach n.

Examples

Example 1

1
 \
 2
 / \
3 4

Input: values = [1, 2, 3, 4], left = [-1, 2, -1, -1], right = [1, 3, -1, -1]
Output: [1, 3, 4, 2]

The root has no left child, so the left boundary is empty. The leaves are 3 and 4. The right boundary is the node with value 2; the leaf 4 that ends it is listed with the leaves. The boundary sum is 10.

Example 2

 1
 / \
 2 3
 / \ /
 4 5 6
 / \ / \
 7 8 9 10

Input: values = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
 left = [1, 3, 5, -1, 6, 8, -1, -1, -1, -1],
 right = [2, 4, -1, -1, 7, 9, -1, -1, -1, -1]
Output: [1, 2, 4, 7, 8, 9, 10, 6, 3]

Node i holds the value i + 1. The left boundary is 2, whose next step reaches the leaf 4. The leaves are 4, 7, 8, 9 and 10. The right boundary from the top is 3, then 6, because 3 has no right child, and it stops at the leaf 10; read from the bottom it is 6, 3. The boundary sum is 50.

Example 3

Input: values = [5], left = [-1], right = [-1]
Output: [5]

A lone root is not a leaf, so it appears once.