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