You did not tag beginner - let me just mention there are deviations from the Style Guide for Python Code.
You show a minimalistic
Node: I added
You chose to tackle "LCA" from nodes that do not allow to get the parent in constant time: interesting.
You chose to solve a problem in a recursive data structure avoiding recursion: oh well.
You start by building a supplementary data structure adding parent information until provably sufficient. I'm all for "early out" in programming.
You can go further down that road by checking first if one node specified is a descendent of the other one.
You implement depth first traversal (right-to-left, without so much as mentioning either).
This may spend fruitless effort limited by the size of the tree, only.
If you do breadth first traversals from the root and both nodes concurrently, you will stay within a constant factor of the minimum node visits required.
lowest_common_ancestor() as presented returns the LCA's
data instead of the node itself - don't do that, use a wrapper where necessary.
Only revisiting the hyperlinked pseudo-code I appreciated how faithfully you transcribed it to Python. I wish you used more comments rather than less, though.
(The Critical Ideas to Think are quite good.)
I think I didn't like the iterative alternative for using O(n) additional space, expected as well as worst case.
Iterable in hopes of seeing whether the approach carries to k-ary trees:
return (self.left, self.right).__iter__()
to_do as that's what I see it used for. If I don't pop the
Nodes whose children I'm about to push, I have all ancestors in the stack. Worst case remains O(n) space, but expected case is linear in the depth of the tree. Trying to work out the details:
# LCA avoiding recursion and O(n) additional space
def lowest_common_ancestor(root, node1, node2):
""" return lowest common ancestor of node1 and node2
in the tree at root, else None.
A node is an ancestor of itself. """
# *if* ready to assume the other node under root, too
# if root is node1 or root is node2
# return root
# if node1 is node2:
# return node1
if None in (root, node1, node2):
# traverse the tree from root
# depth first keeps all ancestors accessible with limited overhead
# right-to-left is a non-consequential implementation artefact
to_do = [root]
# length of to_do including candidate LCA as last element
candidate_len = 0
# the easy part: check if done, push nodes to process
node = to_do[-1]
if node is node1 or node is node2:
if 0 < candidate_len:
candidate_len = len(to_do)
leaf = True
for child in node:
leaf = False
if not leaf:
# the difficult part:
# get rid of nodes processed
# updating candidate_len
# either processed above
# or a parent with all descendants processed
node = to_do.pop()
if not to_do:
check = to_do[-1]
if node not in check: # check is a sibling not yet processed
n = len(to_do)
if n <= candidate_len:
# XXX "knows" exactly one sibling left
candidate_len = n - 1
# (the alternative being a ("branching factor limited")
# search from the end for node's parent
Contributing to my lack of enthusiasm in implementing a proper "parent search": 1)
index(needle) as a common sequence operation, but no
rindex() (as with
bytearray or Java's
int List.lastIndexOf(needle)) 2) such operation using some notion of equality rather than parent.