Minimum distance between two nodes in an N-ary tree

You are given the root of an N-ary tree. Every node has an integer val, unique within the tree, and a list children of its direct children. There are no parent pointers.

Implement:

def min_distance(root: Node | None, u: int, v: int) -> int

Return the number of edges on the path between the node whose value is u and the node whose value is v. If either value is not in the tree, return -1. If u == v and the value exists, return 0.

Constraints

• 0 <= number of nodes <= 10^5
• The tree can be very deep (for example, a single chain), so do not rely on deep recursion.
• One node may be an ancestor of the other.

Example 1

        10
     /   |   \
   20    30   40
  /  \         |
 50   60       70
      |
      80

• min_distance(root, 50, 80) returns 3: the path is 50 → 20 → 60 → 80.
• min_distance(root, 80, 70) returns 5: the path goes up to 10 and down to 70.

Example 2

Same tree. min_distance(root, 20, 80) returns 2, because 20 is an ancestor of 80. min_distance(root, 30, 99) returns -1, because 99 is not in the tree.

Be ready to discuss how you would answer many queries on the same tree quickly.