Turns out that XML::LibXML can do the work for you at the cost of flexibility:
use strict;
use warnings;
use XML::LibXML qw( );
my $parser = XML::LibXML->new();
my $doc = $parser->parse_fh(*STDIN);
my $root = $doc->documentElement();
for my $node ($root->findnodes('//*')) {
print($node->nodePath(), ': ', $node->nodeName(), "\n");
}
/*: OTA_AirSeatMapRS
/*/*[1]: Success
/*/*[2]: SeatMapResponses
/*/*[2]/*[1]: SeatMapResponse
/*/*[2]/*[1]/*[1]: FlightSegmentInfo
/*/*[2]/*[1]/*[1]/*[1]: DepartureAirport
/*/*[2]/*[1]/*[1]/*[2]: ArrivalAirport
/*/*[2]/*[1]/*[1]/*[3]: OperatingAirline
/*/*[2]/*[1]/*[1]/*[4]: MarketingAirline
/*/*[2]/*[1]/*[2]: SeatMapDetails
/*/*[2]/*[1]/*[2]/*: CabinClass
/*/*[2]/*[1]/*[2]/*/*: AirRows
/*/*[2]/*[1]/*[2]/*/*/*[1]: AirRow
/*/*[2]/*[1]/*[2]/*/*/*[1]/*[1]: AirSeats
/*/*[2]/*[1]/*[2]/*/*/*[1]/*[1]/*[1]: AirSeat
/*/*[2]/*[1]/*[2]/*/*/*[1]/*[1]/*[2]: AirSeat
/*/*[2]/*[1]/*[2]/*/*/*[1]/*[1]/*[3]: AirSeat
/*/*[2]/*[1]/*[2]/*/*/*[1]/*[1]/*[4]: AirSeat
/*/*[2]/*[1]/*[2]/*/*/*[1]/*[1]/*[5]: AirSeat
/*/*[2]/*[1]/*[2]/*/*/*[1]/*[1]/*[6]: AirSeat
/*/*[2]/*[1]/*[2]/*/*/*[1]/*[2]: AirRowCharacteristics
/*/*[2]/*[1]/*[2]/*/*/*[2]: AirRow
/*/*[2]/*[1]/*[2]/*/*/*[2]/*[1]: AirSeats
/*/*[2]/*[1]/*[2]/*/*/*[2]/*[1]/*[1]: AirSeat
/*/*[2]/*[1]/*[2]/*/*/*[2]/*[1]/*[2]: AirSeat
...
/*/*[2]/*[2]/*[2]/*/*/*[21]/*[1]/*[5]: AirSeat
/*/*[2]/*[2]/*[2]/*/*/*[21]/*[1]/*[6]: AirSeat
/*/*[2]/*[2]/*[2]/*/*/*[21]/*[2]: AirRowCharacteristics
/*/*[2]/*[2]/*[2]/*/*/*[22]: AirRow
/*/*[2]/*[2]/*[2]/*/*/*[22]/*[1]: AirSeats
/*/*[2]/*[2]/*[2]/*/*/*[22]/*[1]/*[1]: AirSeat
/*/*[2]/*[2]/*[2]/*/*/*[22]/*[1]/*[2]: AirSeat
/*/*[2]/*[2]/*[2]/*/*/*[22]/*[1]/*[3]: AirSeat
/*/*[2]/*[2]/*[2]/*/*/*[22]/*[1]/*[4]: AirSeat
/*/*[2]/*[2]/*[2]/*/*/*[22]/*[1]/*[5]: AirSeat
/*/*[2]/*[2]/*[2]/*/*/*[22]/*[1]/*[6]: AirSeat
/*/*[2]/*[2]/*[2]/*/*/*[22]/*[2]: AirRowCharacteristics
/*/*[2]/*[2]/*[3]: BookingReferenceID
/*/*[2]/*[3]: AirTravelers
/*/*[2]/*[3]/*[1]: AirTraveler
/*/*[2]/*[3]/*[1]/*[1]: PersonName
/*/*[2]/*[3]/*[1]/*[1]/*[1]: GivenName
/*/*[2]/*[3]/*[1]/*[1]/*[2]: MiddleName
/*/*[2]/*[3]/*[1]/*[1]/*[3]: Surname
/*/*[2]/*[3]/*[1]/*[1]/*[4]: NameTitle
/*/*[2]/*[3]/*[1]/*[2]: TravelerRefNumber
/*/*[2]/*[3]/*[2]: AirTraveler
/*/*[2]/*[3]/*[2]/*[1]: PersonName
/*/*[2]/*[3]/*[2]/*[1]/*[1]: GivenName
/*/*[2]/*[3]/*[2]/*[1]/*[2]: MiddleName
/*/*[2]/*[3]/*[2]/*[1]/*[3]: Surname
/*/*[2]/*[3]/*[2]/*[1]/*[4]: NameTitle
/*/*[2]/*[3]/*[2]/*[2]: TravelerRefNumber
/*/*[2]/*[3]/*[3]: AirTraveler
/*/*[2]/*[3]/*[3]/*[1]: PersonName
/*/*[2]/*[3]/*[3]/*[1]/*[1]: GivenName
/*/*[2]/*[3]/*[3]/*[1]/*[2]: MiddleName
/*/*[2]/*[3]/*[3]/*[1]/*[3]: Surname
/*/*[2]/*[3]/*[3]/*[1]/*[4]: NameTitle
/*/*[2]/*[3]/*[3]/*[2]: TravelerRefNumber