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
  • 3
    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
up vote 1 down vote accepted

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.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.