How to build a binary tree using an adjacency list?

Question

Algorithms

Hello everyone, the essence of the question is this: Given an undirected graph in the form of an adjacency list, you need to check whether this graph is a tree, if yes, then return a binary tree built using this list. The question of checking (whether the graph is a tree) has been resolved, but it is not clear how this tree can now be built from the adjacency list.

Answer 1

Detour naturally.

Answer 2

As I understand it, at the input you have an array containing lists of neighbors (indices) for each vertex of the graph.
Take any vertex with a number of neighbors less than or equal to two, and designate it as the root.
For any node, the root of the left subtree will be the first neighbor in the list (if any) that is not the same as the parent. Recursively build the left subtree.
The root of the right subtree will be the second neighbor in the list (if any) that is not the same as the parent.
Recursively build the right subtree.
As a result, get an unsorted unbalanced binary tree