# Critique my python solution?

• ``````class Solution:
# @param {TreeNode} root
# @param {TreeNode} p
# @param {TreeNode} q
# @return {TreeNode}
def lowestCommonAncestor(self, root, p, q):
if root.left:
r = self.lowestCommonAncestor(root.left, p, q)
if r: return r

if root.right:
r = self.lowestCommonAncestor(root.right, p, q)
if r: return r

(has_p, has_q) = self.has_target_descendant(root, p, q)
if has_p and has_q: return root
return None

def has_target_descendant(self, root, p, q):
has_p, has_q = root == p, root == q

if root.left:
(branch_has_p, branch_has_q) = self.has_target_descendant(root.left, p, q)
has_p = branch_has_p or has_p
has_q = branch_has_q or has_q

if root.right:
(branch_has_p, branch_has_q) = self.has_target_descendant(root.right, p, q)
has_p = branch_has_p or has_p
has_q = branch_has_q or has_q

return (has_p, has_q)
``````

I don't think this is a great solution. The running time should be O(n^2) as I do a post-order traversal and each time I check if every child nodes

• I'm not sure about the speed (it's 5am and this is complicated :-), but you can remove some parentheses and duplication:

``````class Solution:

def lowestCommonAncestor(self, root, p, q):
for kid in root.left, root.right:
if kid:
r = self.lowestCommonAncestor(kid, p, q)
if r: return r
return root if all(self.has_target_descendant(root, p, q)) else None

def has_target_descendant(self, root, p, q):
has_p, has_q = root == p, root == q

for kid in root.left, root.right:
if kid:
branch_has_p, branch_has_q = self.has_target_descendant(kid, p, q)
has_p = branch_has_p or has_p
has_q = branch_has_q or has_q

return has_p, has_q
``````

It's also simpler to search just one node at a time, and it even ran faster on the OJ:

``````class Solution:

def lowestCommonAncestor(self, root, p, q):
for kid in root.left, root.right:
if kid:
r = self.lowestCommonAncestor(kid, p, q)
if r: return r
return root if self.has(root, p) and self.has(root, q) else None

def has(self, root, node):
return root and (root == node or
self.has(root.left, node) or
self.has(root.right, node))
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.