```
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
# 1. bfs to search p and q
queue = [root]
parent = {root:None}
while p not in parent or q not in parent:
node = queue.pop(0)
if node.left:
queue.append(node.left)
parent[node.left] = node
if node.right:
queue.append(node.right)
parent[node.right] = node
# 2. nullify all ancestors of p
curr = p
while curr:
tmp = parent[curr]
parent[curr] = None
curr = tmp
# 3. start walking back from q till a None is encountered
curr = q
while parent[curr]:
curr = parent[curr]
return curr
```