Find the common ancestor between two nodes of a tree

Question

Here is my code in Python for to find a common ancestor between two nodes in a particular tree. This is a question from Cracking the Coding Interview that I decided to implement on my own. No one has talked about the solution that I implemented below.

import unittest
from Tree import *
from list2BST import *


def traverse_DFS(root, target_node_value, hash_route):
    # print('looking at node ' + str(root.value))
    if root.value == target_node_value:
        # print('found node ' + str(target_node_value))
        hash_route[root.value] = 1
        return 1
    else:
        if root.left_child:
            left_result = traverse_DFS(root.left_child, target_node_value,
                                       hash_route)
            if left_result == 1:
                hash_route[root.value] = 1
                return 1
        if root.right_child:
            right_result = traverse_DFS(root.right_child, target_node_value,
                                        hash_route)
            if right_result == 1:
                hash_route[root.value] = 1
                return 1


common_ancestor = None


def hash_check_DFS(root, target_node_value, hash_route):
    global common_ancestor

    if root.value == target_node_value:
        if root.value in hash_route:
            print('Found a common ancestor ' + str(root.value))
            if common_ancestor is None:
                common_ancestor = root.value
        return 1
    else:
        if root.left_child:
            left_result = hash_check_DFS(root.left_child, target_node_value,
                                         hash_route)
            if left_result == 1:
                if root.value in hash_route:
                    if common_ancestor is None:
                        print('Found a common ancestor ' + str(root.value))
                        common_ancestor = root.value
                return 1

        if root.right_child:
            right_child = hash_check_DFS(root.right_child, target_node_value,
                                         hash_route)

            if right_child == 1:
                if root.value in hash_route:
                    if common_ancestor is None:
                        print('Found a common ancestor ' + str(root.value))
                        common_ancestor = root.value
                return 1


def find_common_node(Tree, node1, node2):
    global common_ancestor

    print('Running the common ancestry finder')

    # First run DFS v1 with Hash
    hash_route= {}

    print('This value of node1 is ' + str(node1))
    traverse_DFS(Tree.root, node1, hash_route)

    print(hash_route)

    common_ancestor = None
    hash_check_DFS(Tree.root, node2, hash_route)
    if common_ancestor:
        return common_ancestor
    else:
        return None


class Test(unittest.TestCase):

    def test_basic_odd_case(self):
        array = [1, 4, 5, 8, 11, 15, 18]
        result_tree = BinaryTree(insert_list_BST(0, array))
        result_node = find_common_node(result_tree, 1, 18)
        self.assertEqual(result_node, 8)

    def test_basic_even_case(self):
        array = [1, 4, 5, 8, 11, 15, 18, 20]
        result_tree = BinaryTree(insert_list_BST(0, array))
        result_node = find_common_node(result_tree, 1, 8)
        self.assertEqual(result_node, 5)


if __name__ == '__main__':
    unittest.main()

Basically, I do a DFS (depth-first search) of the tree for the first node (Time: \$O(n)\$ and Space: \$O(1)\$) and then I get the recursive callbacks to add the path to a hashmap (Time: \$O(logn)\$ Space: \$O(n)\$). The second time around while using DFS for the second node, once I find it — I check with the hashmap till a collision occurs, indicating the lowest common ancestor.

My Tree class is here, while my list2BST function is here. I am looking for feedback on a couple of things:

• Performance of code and how it could possibly be improved.
• My coding style and the readability of the said code.

Notes

I forgot to mention that the tree does not necessarily have to be a Binary Search Tree. The only condition is that it is a Binary Tree.

Answer 1

You seem to make use often return 1. It would be better to use booleans to show a clear intention of what you want to return.

Also, your hash_route, which you build as a dict, has a constant value that is never used, making it effectively a set, which is fine if all you care is the lowest common ancestor.

I would go for:

def traverse_DFS(root, target_node_value, ancestor_set):
    # print('looking at node ' + str(root.value))
    if root.value == target_node_value:
        # print('found node ' + str(target_node_value))
        ancestor_set.add(root.value)
        return True
    else:
        if root.left_child:
            left_result = traverse_DFS(root.left_child, target_node_value,
                                       ancestor_set)
            if left_result:
                ancestor_set.add(root.value)
                return True
        if root.right_child:
            right_result = traverse_DFS(root.right_child, target_node_value,
                                        ancestor_set)
            if right_result:
                ancestor_set.add(root.value)
                return True
    return False

I would also get rid of common_ancestor global variable (avoid them whenever you can, and also when you think you cannot, since you most probably can anyway). You can easily carry that information in the return value, together with the flag for the found node.

def hash_find_ancestor_DFS(root, target_node_value, ancestor_set):

    if root.value == target_node_value:
        if root.value in ancestor_set:
            return (True, root.value)
        else:
            return (True, None)
    else:
        if root.left_child:
            (found, ancestor) = hash_find_ancestor_DFS(root.left_child, target_node_value,
                                         ancestor_set)
            if found:
                if ancestor:
                    return (True, ancestor)
                elif root.value in ancestor_set:
                    return (True, root.value)
                else:
                    return (True, None)

        if root.right_child:
            (found, ancestor) = hash_find_ancestor_DFS(root.right_child, target_node_value,
                                         ancestor_set)
            if found:
                if ancestor:
                    return (True, ancestor)
                elif root.value in ancestor_set:
                    return (True, root.value)
                else:
                    return (True, None)

    return (False, None)

For completeness, this would be the other function:

def find_common_node(Tree, node1, node2):
    print('Running the common ancestry finder')

    # First run DFS v1 with Hash
    hash_route= set()
    print('This value of node1 is ' + str(node1))
    found = traverse_DFS(Tree.root, node1, hash_route)

    if not found:
        return None
    print(hash_route)
    (found, common_ancestor) = hash_find_ancestor_DFS(Tree.root, node2, hash_route)

    return common_ancestor

I added a check to shortcut the second search if the node is not found in the first.

Answer 2

Code readability and style

Your code has nothing wrong with style (as far as I know). It seems to be (99.9999...%) PEP 8 compliant.

I ran a PEP 8 checker over your code and this is what it picked up -

Which basically tells you to add a space before the operator '=' here -

hash_route= {}
# hash_route = {}

As for the missing newline at the end of the file - there is no Python specific reason why you have to do this. It's just that most people tend to do this. pylint's help page on that message tells you more about it:

While Python interpreters typically do not require line end character(s) on the last line, other programs processing Python source files may do, and it is simply good practice to have it. This is confirmed in Python docs: Line Structure which states that a physical line is ended by the respective line end character(s) of the platform.

---

Now let's introduce you to f-strings -

To create an f-string, prefix the string with the letter “ f ”. The string itself can be formatted in much the same way that you would with str.format(). f-strings provide a concise and convenient way to embed python expressions inside string literals for formatting.

Which means, instead of using the outdated way of formatting strings -

print('Found a common ancestor ' + str(root.value))

You could simply write it out as -

print(f'Found a common ancestor {root.value}')

Also, good use of the if __name__ == __'main__': guard. Most people don't even attempt to use it.

---

Another thing PEP 8 says that -

Comparisons to singletons like None should always be done with is or is not, never the equality operators.

which you have implemented really well. Most people don't do this (including me). You can read more about it here.

---

Overall, in terms of code readability and style, this is a well-built code (probably needs more work on performance). Good work!

Hope this helps!

Answer 3

The main piece of advice I feel I can offer is to avoid using the asterix from list2BST import *

This makes it much harder for other users to work out where individual functions are coming from. It is much better practice to say

import list2BST

and then

list2BST.<function name>

or from list2BST import <function_1>, <function_2>

I have copied below my own implementation of this if you are interested in looking. The code is much shorter and I build, print and search the BST in a single module. I also use fewer variables and I think my approach is fairly intuitive. I have added this for comparison though because other than my comment above, I cannot think of anything else you can do to improve your code

""""Module to find lowest common ancestor of BST"""
from dataclasses import dataclass


@dataclass
class Node:
    """BST class"""

    value: int
    left: None = None
    right: None = None

    def add_child(self, value):
        """Add child to BST"""
        if self.value:
            if value < self.value:
                if self.left:
                    self.left.add_child(value)
                else:
                    self.left = Node(value)
            else:
                if self.right:
                    self.right.add_child(value)
                else:
                    self.right = Node(value)

    def print_tree(self, level=0):
        """Print the BST"""
        if self.value:
            print(" " * level, self.value)
            if self.left:
                self.left.print_tree(level + 1)
            if self.right:
                self.right.print_tree(level + 1)

    def explore(self, node, lst_ancestors):
        """Explore BST to find ancestors of node"""
        if self.value:
            if self.value == node:
                lst_ancestors.append(self.value)
                return True, lst_ancestors
            if self.left:
                left_true = self.left.explore(node, lst_ancestors)
                if left_true:
                    lst_ancestors.append(self.value)
                    return True, lst_ancestors
            if self.right:
                right_true = self.right.explore(node, lst_ancestors)
                if right_true:
                    lst_ancestors.append(self.value)
                    return True, lst_ancestors

    def common_ancestor(self, node1, node2):
        """Find common ancestors"""
        _, list_1 = self.explore(node1, [])
        _, list_2 = self.explore(node2, [])
        common_nodes = set(list_1).intersection(list_2)
        if common_nodes:
            print(f"The LCA node of {node1} and {node2} is {list(common_nodes)[0]}")
        else:
            print(f"There is no LCA for {node1} and {node2}")


if __name__ == "__main__":
    n = Node(5)
    n.add_child(3)
    n.add_child(4)
    n.add_child(2)
    n.add_child(7)
    n.add_child(6)
    n.add_child(8)

    node1 = 2
    node2 = 6
    n.common_ancestor(node1, node2)