Lowest Common Ancestor in Binary Tree using recursion

Question

I am trying to implement the solution to the problem Lowest Common Ancestor(LCA) of Binary Tree via top-down recursion.

The approach I have used is:

IDEA: Find the node which has one of the desired nodes in either subtree while the other desired node is the opposite subtree.

PSEUDOCODE
1. If the value of root is equal to either of the desired node's value, 
   the root is the LCA.
2. Search in the left subtree for either node.
3. Search in the right subtree for either node.
4. If neither of them contains any of the two nodes,
   the nodes do not exist in the tree rooted at the root node.
5. If each of them contains one node,
   the root is the LCA.
6. If either one of them contains a node,
   return it to the root.

This is what has also been recommended in answers of related questions on StackOverflow.
Now, this code works well if we assume all the nodes of the tree to be of unique value. In other words, this approach seems to break in case of duplicates (or, is it just my implementation?)

I would like to know how can I fix my code to work with duplicate values as well. If this approach cannot result in the optimal solution, how should I alter my approach?

Here is the exact implementation:

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

    def __repr__(self):
        return 'TreeNode({}, {}, {})'.format(self.val, self.left, self.right)

def lowestCommonAncestor(root, p, q):
    """
    :type root: TreeNode
    :type p: TreeNode
    :type q: TreeNode
    :rtype: TreeNode
    """
    if root is None:
        return None

    if p.val == root.val or q.val == root.val:
        return root

    left_subtree = lowestCommonAncestor(root.left, p, q)
    right_subtree = lowestCommonAncestor(root.right, p, q)

    if left_subtree is None and right_subtree is None:
        return None

    if left_subtree is not None and right_subtree is not None:
        return root

    if left_subtree is None:
        return right_subtree
    else:
        return left_subtree

For example:

root = TreeNode(2)
root.left = TreeNode(3)
root.left.left = TreeNode(1)
root.right = TreeNode(5)
root.right.left = TreeNode(7)
root.right.right = TreeNode(1)
print(lowestCommonAncestor(root, TreeNode(1), TreeNode(7)))

This returns the root of the tree as the result. result = TreeNode(2)

No doubt, the root is always an ancestor.
However, there exists a "lower" common ancestor than the root - TreeNode(5).

Answer 1

You have some problems: 1) Why are you checking for Node.val? You should be able to just compare one Node with another Node directly. That should solve issues when you have a tree with multiple nodes which have the same value... assuming that is your only problem.

2) Why do you return root if the left subtree is non-empty and the right subtree is non-empty? In many cases, of course, that will return root. This is generally not the behavior we want.

You may want to rethink your algorithm from scratch (you have some nice ideas going, but now that you see you've made some mistakes and since this problem is fairly simple/straightforward, it might be more beneficial to think afresh).

A suggestion: since this problem is a problem on trees, and has to do with search/paths, consider the problem of finding a path from Node p to Node q. We know that in a tree, there exists exactly one path from any two nodes (this simply follows from the fact that a tree is a connected acyclic graph, by definition).

You might keep this idea in mind when going back up after recursing to a base case, or after recursing to a base case you might want to create a data structure to store visited nodes in a loop then test some conditions and maybe recurse more (essentially a DFS approach vs a BFS approach, while the BFS approach uses explicit memoization / added memory, whereas DFS uses the stack to remember things).

Answer 2

The code will look like this

def lowestCommonAncestor(root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
flag=0
if root is None:
    return None

if p.val == root.val or q.val == root.val:
    flag=1
    #return root

left_subtree = lowestCommonAncestor(root.left, p, q)
right_subtree = lowestCommonAncestor(root.right, p, q)

if left_subtree is None and right_subtree is None:
    if flag==0:
        return None
    else:
        return root

if left_subtree is not None and right_subtree is not None:
    return root

if left_subtree is None:
    if flag==1:
        if (right_subtree.value!=p && right_subtree.value!=q) || right_subtree.value==root.value:
            return right_subtree
        elif right_subtree.value!=root.value:
            return root
    else:
        return right_subtree
else:
    if flag==1:
        if (left_subtree.value!=p && left_subtree.value!=q) || left_subtree.value==root.value:
            return left_subtree
        elif left_subtree.value!=root.value:
            return root
    else:
        return left_subtree

Answer 3

The idea is like this: we recursively search p and q in root's left and right subtree. If the result of the left subtree is null, then it means p and q is not in root's left so we could safely conclude that the LCA must reside in root's right subtree. Similar conclusion holds true if the result of right subtree is null. But if neither of them is null, that indicates that p and q take either side of the root. Therefore, root is the LCA.

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return root;
        }

        if (root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right= lowestCommonAncestor(root.right, p, q);

        if (left != null && right != null) {
            return root;
        } else if (left != null) {
            return left;
        } else {
            return right;
        }
    }
}