11
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Since you are owner of the Tree and BinaryTree classes, is it possible to to change the implementation and add a Parent reference to them? In other words, is there a reason you did not include this property? \$\endgroup\$ – dfhwze Jun 17 at 6:33
  • \$\begingroup\$ There is no particular reason except for the fact that a parent pointer is usually not common (from my limited experience). I am the owner of both those classes, yes. How would having a pointer to the parent improve performance? \$\endgroup\$ – Sharan Duggirala Jun 17 at 8:34
  • 3
    \$\begingroup\$ By traversing both nodes up the ancestor list until a match in ancestors is found. This way, you don't need to traverse the entire tree all the time. \$\endgroup\$ – dfhwze Jun 17 at 8:42
  • \$\begingroup\$ Not sure what libraries/environments you work with, in things like Unity (3D engine), objects typically have a reference to their parent. Having a reference to the parent is probably much more common than you think, for the reason @dfhwze mentioned \$\endgroup\$ – Mars Jun 18 at 2:48
  • 1
    \$\begingroup\$ Yeah it would ;p \$\endgroup\$ – Mars Jun 18 at 10:54
5
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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 -

enter image description here

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ @SharanDuggirala - I have removed the content. I have left anything that might help you. Hope this helps! \$\endgroup\$ – Justin Jun 17 at 4:27
  • 1
    \$\begingroup\$ Thanks for the compliment on using the __name__ == '__main__'. I believe that it is essential for using the Python style unit testing? \$\endgroup\$ – Sharan Duggirala Jun 17 at 4:29
  • 1
    \$\begingroup\$ @SharanDuggirala - Yes, it is. \$\endgroup\$ – Justin Jun 17 at 4:30
  • 3
    \$\begingroup\$ I believe there is some part of POSIX that specifies that text files end with a newline. So, if you don't have the newline, then your file is technically not a text file, which means that technically, the OS is not required to process it as a script, which means that if some OS vendor is an extreme stickler for the rules, then a shebang line will not work. (Although the shebang line isn't specified anywhere, so such an extreme OS will probably not implement them anyway.) \$\endgroup\$ – Jörg W Mittag Jun 17 at 13:00
  • 3
    \$\begingroup\$ @JörgWMittag Yes, it’s a POSIX rule. However, the implication isn’t that the system could legally refuse to treat it as a script (at least I’m not aware of any such rule, even implicitly). Rather, the issue is simply that some tools will not correctly handle the file; for instance, a conforming sed implementation might not handle the last line. In practice, up to date GNU sed and BSD sed both do (though slightly differently). \$\endgroup\$ – Konrad Rudolph Jun 17 at 13:04
2
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ @SharanDuggirala I have included my code for this problem too for comparison \$\endgroup\$ – EML Jun 18 at 12:37

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.