First of all, I would definitely say, use XPath expressions to do everything.   Use a libxml2-based Perl package.

Second, you might need to take a “branch and bound” type of approach:   use one set of expressions to carve the total data structure into big-chunks that you can iterate through, and then, within each subtree that you find, use other XPaths to find nodes-of-interest.   Having found one, your Perl logic may need to do some tree-walking to see if “these are the droids you’re looking for.”   But, let XPath do as much of the work for you as possible.