2
\$\begingroup\$

In the below code I've implemented a method to find the lowest common ancestor of a binary tree.

This is an iterative approach using this pseudocode.

Please suggest any improvements that can be made.

class Node:
    def __init__(self, data=None, left=None, right=None):
        self.data  = data
        self.left  = left
        self.right = right

def lowest_common_ancestor(root, node1, node2):
    parent = {root: None}
    stack = [root]

    while node1 not in parent or node2 not in parent:
        node = stack[-1]
        stack.pop()
        if node.left:
            parent[node.left] = node
            stack.append(node.left)
        if node.right:
            parent[node.right] = node
            stack.append(node.right)

    ancestors = set()
    while node1:
        ancestors.add(node1)
        node1 = parent[node1]
    while node2 not in ancestors:
        node2 = parent[node2]

    return node2.data

def main():
    '''
    Construct the below binary tree:

            30
           /  \
          /    \
         /      \
        11      29
       /  \    /  \
      8   12  25  14

    '''
    root = Node(30)
    root.left  = Node(11)
    root.right = Node(29)
    root.left.left  = Node(8)
    root.left.right = Node(12)
    root.right.left  = Node(25)
    root.right.right = Node(14)

    print(lowest_common_ancestor(root, root.left.left, root.left.right))       # 11
    print(lowest_common_ancestor(root, root.left.left, root.left))             # 11
    print(lowest_common_ancestor(root, root.left.left, root.right.right))      # 30


if __name__ == '__main__':
    main()

\$\endgroup\$
2
\$\begingroup\$

Unit tests

Turn these:

print(lowest_common_ancestor(root, root.left.left, root.left.right))       # 11
print(lowest_common_ancestor(root, root.left.left, root.left))             # 11
print(lowest_common_ancestor(root, root.left.left, root.right.right))      # 30

into assertions of the form assert 11 == ..., and you'll immediately have a unit test, which is generally of greater value.

Pop

node = stack[-1]
stack.pop()

should not be necessary; that's what pop already does:

node = stack.pop()
\$\endgroup\$
1
\$\begingroup\$

You did not tag - let me just mention there are deviations from the Style Guide for Python Code.
You show a minimalistic Node: I added
def __repr__(self):
return '‹'+str(self.left)+'#'+str(self.data)+'#'+str(self.right)+'›'

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.
I made Node an Iterable in hopes of seeing whether the approach carries to k-ary trees:
def __iter__(self):
return (self.left, self.right).__iter__()
I renamed stack 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):
        return None

    # 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

    while to_do:
        # 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:
                return to_do[candidate_len-1]
            candidate_len = len(to_do)
        leaf = True
        for child in node:
            if child:
                leaf = False
                to_do.append(child)
        if not leaf:
            continue
        # the difficult part:
        #  get rid of nodes processed
        #  updating candidate_len
        while True:
            # either processed above
            # or a parent with all descendants processed
            node = to_do.pop()
            if not to_do:
                return None
            check = to_do[-1]
            if node not in check:  # check is a sibling not yet processed
                break
        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
    return None

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.

\$\endgroup\$
2
  • \$\begingroup\$ I would have preferred __str__(self) over repr if that was effective in my IDE. \$\endgroup\$ – greybeard Nov 6 '20 at 8:14
  • \$\begingroup\$ Didn't manage to code concurrent traversals or minimum comparison search without ugly code multiplication. \$\endgroup\$ – greybeard Nov 22 '20 at 21:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.