How to handle a tree given in an array of pairs?

Question

I'm struggling with finding the best of handling tree problems where the input is given as an array/list of pairs.

For example a tree is given as input in the format: [(1,3),(1,2),(2,5)(2,4),(5,8)] Where the first value in a pair is the parent, and the second value in a pair is the child.

I'm used to being given the root in tree problems. How would one go about storing this for problems such as "Lowest Common Ancestor"?

Answer 1

It depends on which problem you need to solve. For the problem of finding the lowest common ancestor of two nodes, you'll benefit most from a structure where you can find the parent of a given node in constant time. If it is already given that the nodes are numbered from 1 to n (without gaps), then an array is a good structure, such that arr[child] == parent. If the identifiers for the nodes are not that predictable, then use a hashmap/dictionary, such that map.get(child) == parent.