Bits of Py.

If the implementation is hard to explain, it's a bad idea

Wed 12 July 2017

Finding the Lowest Common Ancestor in a Binary Tree.

Posted by marodrig in algorithms   

How to find the lowest common ancestor(LCA) in a tree.

There are two approaches we can use when looking for the Lowest Common Ancestor in a binary tree. We can use a parent member in our TreeNode class, or we can do without this extra member. In this post I will be using the parent member in our class to help with finding the LCA.

Let's take a look at our TreeNode class definition:

    class TreeNode:
        def __init__(self, value):
            self.value = value
            self.left = None
            self.right = None
            self.parent = None

Our TreeNode has the following data members: value, left, right and parent. Our value will hold our data. The left will reference our left child node, right our right child node, and parent will be our parent node. The root of the tree will have a parent of None.

Our basic approach when looking for the lowest common ancestor will be to compare the values of each node, if values are different, we traverse upward using the parent member of each node.

    while node_1.value != node_2.value:
        node_1 = node_1.parent
        node_2 = node_2.parent
    return node_1.value

But we have a problem. This works only if our node_1 and node_2 are on the same level. If either node is the LCA we are looking for, we are toast. If one is node a level above or below the other node, we are toast. We need to go back to the drawing board and figure out something new. How can we know both nodes are on the same level?

We know that by definition if the depth of to nodes are the same, they must be on the same level! We can use this to figure out when node_1 and node_2 are not on the same level. But first we need to create a method to calculate the depth of a given node:

    def get_depth_node(node):
        depth = 0
        while node:
            depth += 1
            node = node.parent
        return depth

Our method simply increases a depth variable while traversing up the tree using the parent member from our TreeNode class. Then returns once we hit the root node.

This is a big help for our algorithm. We know have a way to find the depth of each node. Now we need to do a couple of things:

  • Find the node that is at the greatest depth in the tree, or in other words, the one farthest down the tree.
  • Figure out how much farther it is in comparison to our other node.
  • Figure out how to bring it level to our second node.
  • At this point our original algorithm can take over and find the LCA.

Our first step is to get the depth of each node. Lets assume node_1 is the node farthest down the tree. We then want to get the absolute value of the difference between depths of each node. And move up the tree from the node farthest down until the difference is 0. This means we are at the same level.

    lowest_node = node_1
    highest_node = node_2

    depth_node_1 = get_depth_node(node_1)
    depth_node_2 = get_depth_node(node_2)

    if depth_node_2 > depth_node_1:
        lowest_node = node_2
        highest_node = node_1

    depth_diff = abs(depth_node_1 - depth_node_2)
    while depth_diff > 0:
        lowest_node = lowest_node.parent
        depth_diff -= 1

We also check which depth is the largest one, and we change the reference to the node that is farthest down the tree. Once we have all this set in place, we can use our original idea without issues.

    def find_lca_using_parent(node_1, node_2):

        lowest_node = node_1
        highest_node = node_2

        depth_node_1 = get_depth_node(node_1)
        depth_node_2 = get_depth_node(node_2)

        if depth_node_2 > depth_node_1:
            lowest_node = node_2
            highest_node = node_1

        depth_diff = abs(depth_node_1 - depth_node_2)
        while depth_diff > 0:
            lowest_node = lowest_node.parent
            depth_diff -= 1

        while lowest_node.value != highest_node.value:
            lowest_node = lowest_node.parent
            highest_node = highest_node.parent

        return lowest_node

And this is the complete algorithm for finding the LCA of two nodes using a parent member in the TreeNode class.

Summary

  • Having a parent member in our TreeNode class help to calculate depth at each node, and finding the lowest common ancestor.
  • Traversing up from each node up to the parent only works if we are at the same level.
  • If the depth of each node is the same, we know we are at the same level.
  • We need the difference of both depths to be equal to 0 for our traversal upward using the parent member to work.
  • We need to identify the node with the greatest depth first, and bring it level to the other node.