Build a Tree From a Parent Array

A tree with n nodes numbered 0 to n-1 is described by a list parent where parent[i] is the number of node i's parent, and parent[r] == -1 for the single root r. Every node has at most two children. Build the tree with node i holding the value i, following this rule: when a node has two children the one with the smaller number is the left child; a node with a single child gets it as the left child. Return the root.

Examples

       1
      / \
     0   2
    /
   3

Input:  parent = [1, -1, 1, 0]
Output: tree_to_list(...) == [1, 0, 2, 3]

Input:  parent = [-1, 0, 0, 1, 1, 2]
Output: [0, 1, 2, 3, 4, 5]

Constraints

• 0 <= n <= 1000
• parent describes a valid binary tree with exactly one root when n > 0

Goals

• Create all nodes before linking them so parents can be referenced in any order
• Apply a tie-breaking rule that makes the child positions unique