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 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.