In Python ElementTree how can I get list of all ancestors of an element in tree?

Question

I need "get_ancestors_recursively" function.
A sample run can be

>>> dump(tr)
<anc1>
  <anc2>
    <element> </element>
  </anc2>
</anc1>
>>> input_element = tr.getiterator("element")[0]
>>> get_ancestors_recursively(input_element)
['anc1', 'anc2']

Can somebody help me with this ?

Answer 1

Another option is LXML, which provides useful extensions to the built in ElementTree api. If you're willing to install an external module, it has a nice Element.getparent() function that you could simply call recursively until reaching ElementTree.getroot(). This will probably be the fastest and most elegant solution (as the lxml.etree module introduces pointer attributes for the Elements that point to their parents, so instead of searching the entire tree for the proper parent/child pairs).

Answer 2

In the latest version of ElementTree (v1.3 or later), you can simply do

input_element.find('..')

recursively. However, the ElementTree that ships with Python doesn't have this functionality, and I don't see anything in the Element class that looks upwards.

I believe this means you have to do it the hard way: via an exhaustive search of the element tree.

def get_ancestors_recursively(e, b):
    "Finds ancestors of b in the element tree e."
    return _get_ancestors_recursively(e.getroot(), b, [])

def _get_ancestors_recursively(s, b, acc):
    "Recursive variant. acc is the built-up list of ancestors so far."
    if s == b:
        return acc
    else:
        for child in s.getchildren():
            newacc = acc[:]
            newacc.append(s)
            res = _get_ancestors_recursively(child, b, newacc)
            if res is not None:
                return res
        return None

This is slow because of the DFS, and cranks out a lot of lists for garbage collection, but if you can deal with that it should be fine.