Medium · Trees

N-ary tree distance of two nodes

Given the root of an n-ary tree whose node labels are unique, and two nodes a and b in it identified by their labels, return the number of edges on the path between a and b.

Examples

Example 1

{
  "nodes": [
    {"label": "1", "children": [1, 2, 3]},
    {"label": "2", "children": [4, 5]},
    {"label": "3", "children": []},
    {"label": "4", "children": [6]},
    {"label": "5", "children": [7]},
    {"label": "6", "children": []},
    {"label": "7", "children": []},
    {"label": "8", "children": []}
  ],
  "a": 8,
  "b": 7
}

Output: distance 5

Example 2

{
  "nodes": [
    {"label": "1", "children": [1, 2, 3]},
    {"label": "2", "children": [4, 5]},
    {"label": "3", "children": []},
    {"label": "4", "children": [6]},
    {"label": "5", "children": [7]},
    {"label": "6", "children": []},
    {"label": "7", "children": []},
    {"label": "8", "children": []}
  ],
  "a": 8,
  "b": 6
}

Output: distance 3

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.