# Time complexity of common ancestor algorithm

I have an algorithm here to find the common ancestor of two nodes in a binary tree.

def commonAncestor(self, nodeA, nodeB, root):
#checking if nodeB is a descendant of nodeA
checkLeft = self.checkSubtree(nodeA, nodeB, root.leftChild)
checkRight = self.checkSubtree(nodeA, nodeB, root.rightChild)
if checkLeft == 1 and checkRight == 1:
return root
else:
if checkLeft == 2:
# pdb.set_trace()
result = self.commonAncestor(nodeA, nodeB, root.leftChild)
if checkRight == 2:
result = self.commonAncestor(nodeA, nodeB, root.rightChild)
else:
raise ValueError("One of the values you have entered is not in the binary tree")

return result

def checkSubtree(self, nodeA, nodeB, node):
res = 0 #res is being initialized as a separate variable each time
if node is None:
return 0
if node is nodeA or node is nodeB:
res += 1
res += self.checkSubtree(nodeA, nodeB, node.leftChild)
res += self.checkSubtree(nodeA, nodeB, node.rightChild)
return res


I think that the runtime of this algorithm is $O(\log^2 n)$. The first algorithm will run $O(\log n)$ times because it recurses through the binary tree, touching every node, and it subsequently calls the second function on each recursion which again recurses $O(\log n)$ times, correct?

I know this is a not an efficient algorithm, so how do I go about improving this? Specifically, I want to know how to approach the problem of thinking about how to improve this versus just seeing the code of the improved version.

Definition of node class

class TreeNode():
def __init__(self, val, left=None, right=None):
self.value = val
self.leftChild = left
self.rightChild = right

def insertLeftChild(self, val):
self.leftChild = val

def insertRightChild(self, val):
self.rightChild = val

def hasLeftChild(self):
return self.leftChild is not None

def hasRightChild(self):
return self.rightChild is not None

• The runtime $O(\lg^k n)$ is not possible for this problem unless you guarantee that the tree is balanced. The degenerate case that the tree is a path shows that without constraints on the tree the problem is $\Omega(n)$. – Peter Taylor Jul 14 '17 at 9:53

The runtime of the code in the post is $Ω(n)$, even if the tree is balanced, because checkSubtree has to visit all the nodes in the subtree.
In the worst case (where none of the nodes has a left child), the code is the post is $O(n^2)$ for the same reason.
So if you are going to visit all $n$ nodes, you might as well do this in just one pass over the tree, to make sure that you don't have quadratic behaviour in the worst case. See this answer for how to go about it.