python lowest common ancestor
algorithm, python, tree
Solution
Under the assumption that you cannot amend your tree to include depth, you can do the following:
For each Node, recursively traverse the tree upwards until you hit the root. At each parent node, insert the node into a `list`. This should give you `list_a` and `list_b`. Iterate over the shortest list, comparing elements from each list. When you find one that doesn't match, the previous entry is your largest parent element.
Problem
What is the easiest way to implement lowest common ancestor in Python? I have a tree which is represented by each node having a pointer to its parent, and I want to be able to find the first common ancestor given two nodes. I've come up with several ideas but none are particularly appealing Have each node contain a list of its bases, and to perform a join, find the longest common prefix and then take the last element. Unfortunately, I don't know of any builtin way to do longest common prefix so this requires manual looping. Have each node contain a set of its bases and perform a set intersection, and take the maximum element. But this requires defining custom comparison operators, and I'm not even sure if it would work. What should I do? I'm looking for something that favors simplicity over performance, so solutions requiring complicated processing are out. Edit: I discovered that while there isn't a builtin way, you can do longest common prefix in one line using zip, so it's still fairly simple. ``` common = [x for x in zip(*baselists) if len(set(x)) == 1][-1] ```