Finding the common ancestor in the tree - Part 2 [reviewed]

Problem

You are given a Binary Tree (not BST) along with two pointers to nodes somewhere in the tree.

Your algorithm should returns the pointer to the common parent to given nodes.

For example, in the following tree

Figure 1. Binary Search Tree example

The common ancestor of "d" and "f" is "a".

This is another variation of the "Finding a common ancestor in the tree problem"

Unlike the Binary Search Tree, Binary Tree does not offer the pointer to the parent, which makes this question trickier than Part 1.

However, basic algorithm is the same as the original problem in Part 1.

1. You need to know the depth of the given input nodes.
2. You need to chase up the parent nodes for given input nodes during the the comparison step.

Problem is how we can achieve these two things without the help of the parent pointer.

We can use DFS (Depth First Search) algorithm with additional Stack to remember the parents encountered during the search.
Basically, we can perform the DFS to first find the each node given as input. In doing so, we can keep track of the nodes that we encountered. If the backtracking happens, we can pop the node as well.

Once, DFS is done for both nodes, each of which takes O(N) time, where N is the number of nodes in the tree.
We also obtain two stack with list of parents DFS found while searching for the nodes.

Once this step finish, searching the common ancestor is quite straightforward. Only difference is that we pop the parent from the stack instead of referencing the parent pointer.

Here is the complete code running in O(N) as opposed to O( log N) in Part 1.



Practice statistics

40 mins: write up the code based on the algorithm (algorithm was right but implementation was wrong)
12 mins: to find the critical logical flaw in the code and fix up the typos through compilation

UPDATE(2019-07-29): Solved the problem again.

Here is rough algorithm: Given two target node, p1, p2.

• search p1 in the binary tree while adding the parents encountered to p1_parents: $O(log N)$
• search p2 in the binary tree while adding the parents encountered to p2_parents: $O(log N)$

• iterate over two list from the end and find the common ancestor.  

         - check if both nodes are the same. If so, we found a common ancestor
         
           Case1: if the positions of two lists are different, only decrease the index of larger one
           Case2: if the positions of two lists are same, decrease both index by 1.

Overall, running time is O(N). N is the number of nodes in the tree.

Here is a solution in python.


Practice statistics

7:42: to come up with algorithm
14:00: to write the code
2.40: to review and fix a bug

9:00: to write the test code and fix a logical bug and typos (after running)