Reachability Tree Build

Problem

Build a BFS tree of an undirected graph from a root and return parent and depth arrays.

Neighbors are explored in ascending order and unreachable nodes keep parent -1 and depth -1. The root is its own parent with depth 0. edges is a list of [u, v] pairs. Return [parent, depth].

Hint

A BFS tree captures shortest-path structure from the root.

Test cases

case 1

in: [4,[[0,1],[0,2],[1,3]],0]

expected: [[0,0,0,1],[0,1,1,2]]

case 2

in: [3,[[0,1],[1,2]],1]

expected: [[1,1,1],[1,0,1]]

case 3

in: [4,[[0,1],[2,3]],0]

expected: [[0,0,-1,-1],[0,1,-1,-1]]

Starter codePython

def reachability_tree(n, edges, root):
    # Your code here
    pass

3 test cases · run your code against them in the editor