Constructing a binary tree from a list of its edges (node pairs)

I'd like to construct a binary tree from a quite unusual input. The input contains:

1. Total number of nodes.

2. The integer label of the root.

3. A list of all edges (vertices/nodes that are connected to each other). The edges in the list are UNSORTED, there is only one rule for determining left/right children - the child in the edge that appears first in list is always on the left. The order of child/parent in the vertices pair is also random.

I've come up with some straighforward solutions but they require multiple searches through the list of all edges (I'd basically find the 2 edges that have the labeled root in them and repeat this process for all the subtrees.)

I imagine this straightforward approach would be VERY inefficient for trees with a big amount of nodes, but I can't come up with anything else.

Any ideas for more efficient algorithms to solve this?

Here's an example for better visualization:

INPUT: 5 NODES, ROOT LABELED 2, LIST OF EDGES: [(1,0),(1,2),(2,3),(1,4)]

The tree would look like this:

        2
    1       3
 0     4