### Python 3 code to find the Lowest Common Ancestor of a Binary Tree

This is a Non Recursive solution using DFS method.

```class Node():
def __init__(self, val, left = None, right = None):
self.val = val
self.left = left
self.right = right

class Tree():
def __init__(self, root = None):
self.root = root

def lowestCommonAncestor(self, root, p, q):
"""
:type root: Node
:type p: Node
:type q: Node
:rtype: Node
"""

if not root or not p or not q:
return None

if root is p or root is q:
return root

# We are going to perform a single DFS to find both p and q
# So, the time complexisty in worst case is O(n)
lca, stack = [None], [root]
found_one = False
while stack:
node = stack.pop()

# Check if we are coming back up the tree.
# If yes, just pop and continue the loop
lca_popped = lca.pop()
if lca_popped == node:
if node == p or node == q:
found_one = False
else:
if lca_popped:
lca.append(lca_popped)

lca.append(node)
stack.append(node)
# Append the current node to stack
# if we haven't yet found p or q.

stack.extend(filter(None, [node.right, node.left]))
# append right first, so left will be popped first

if node == p or node == q:
found_one = True
# Set p or q to None when found
if node == p:
p = None
if node == q:
q = None

# Check if both p and q have been found
if not p and not q:
return lca.pop()

return None

# Construct the tree
#
#         _______3______
#        /              \
#     ___5__          ___1__
#    /      \        /      \
#    6      _2       0       8
#          /  \
#          7   4

n7 = Node(7)
n5 = Node(5, Node(6), Node(2, n7, Node(4)))
n1 = Node(1, Node(0), Node(8))
root = Node(3, n5, n1)

t = Tree(root)

print('LCA of 5 & 7:')
result = t.lowestCommonAncestor(root, n5, n7)
if result:
print(result.val)
else:
print('None')

print('LCA of 5 & 1:')
result = t.lowestCommonAncestor(root, n5, n1)
if result:
print(result.val)
else:
print('None')```
```        _______3______
/              \
___5__          ___1__
/      \        /      \
6      _2       0       8
/  \
7   4

Output:

LCA of 5 & 7:
5
LCA of 5 & 1:
3```

Hope it helps.

This site uses Akismet to reduce spam. Learn how your comment data is processed.