# Bit trick to solve LCA in Python

• 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:

1. `p` and `q` are in the different subtree of this `node`
2. `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
``````

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