If the `node`

is the Lowest Common Ancestor of the two given nodes `p`

and `q`

, this `node`

must has one of the properties below:

`p`

and`q`

are in the different subtree of this`node`

`node`

itself is one of`p`

or`q`

, and the other given node is in`node`

's subtree

That is, the LCA cannot have both `p`

and `q`

in the same subtree.

Based on this fact, we can mark each node with a marker when we search for the target `p`

and `q`

.

We mark the current node with `0b001`

if the target node is in the current node's left subtree

We mark the current node with `0b010`

if the target node is in the current node's right subtree

We mark the current node with `0b100`

if the target node is the current node.

Then we traverse all the nodes we marked, there would only be one marked node with a marker that has two bit `1`

, which would be exactly the LCA we want!

```
def lowestCommonAncestor(self, root, p, q):
def traverseMark(node, target):
if not node:
return False
if node == target:
markerHash[node] = markerHash.get(node, 0) | 4
return True
if traverseMark(node.left, target): # if target is in the left subtree
markerHash[node] = markerHash.get(node, 0) | 1
return True
elif traverseMark(node.right, target): # if target is in the right subtree
markerHash[node] = markerHash.get(node, 0) | 2
return True
return False
markerHash = {}
traverseMark(root, p)
traverseMark(root, q)
for node in markerHash:
if markerHash[node] in (3,5,6):
return node
return None
```