Time complexity of common ancestor algorithm

Question

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

• Peter Taylor: 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)\$.

Answer 1

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.