### 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) if not found_one: 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.