# Different python O(N) solution, easier to code in an interview than other methods

• The idea is using dfs to find the two paths to p and q respectively, and compare the two paths one by one until they don't agree. The code is longer than other solutions, but runs in O(N) and is extremely easy to come up with in an interview.

``````class Solution(object):
def lowestCommonAncestor(self, root, p, q):
pathp, pathq = [], []
self.helper(root, p, [], pathp)
self.helper(root, q, [], pathq)
i = 0
self.pathp, self.pathq = pathp[0], pathq[0]
# compare the two paths one by one, until one goes out of range or the two don't equal
while i < len(self.pathp) and i < len(self.pathq) and self.pathp[i] == self.pathq[i]:
i += 1
return self.pathp[i-1]

def helper(self, root, p, path, pathp):
# put the final path into pathp
if root is None:
return
if root == p:
pathp.append(path + [p])
return
path.append(root)
self.helper(root.left, p, path, pathp)
self.helper(root.right, p, path, pathp)
path.pop()
``````

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