Oct 1, 2020
diff --git a/Trees/P06_LCAinBinaryTree.py b/Trees/P06_LCAinBinaryTree.py
 # LCA - least common ancestor
 # The lowest common ancestor of two nodes n1 and n2 is the lowest node in tree that has both n1 and n2 as descendants.


 class node:
    def __init__(self,key):
        self.key=key
        self.left=None
        self.right=None

 def lca(root,n1,n2):
    if root is None:
        return None

    if root.key == n1 or root.key == n2:
        return root

    left = lca(root.left, n1, n2)
    right = lca(root.right, n1, n2)

    if left and right:
        return root

    return left if left else right


 # Consider the following binary tree

 #                  3
 #               /     \
 #             6         8
 #           /   \         \
 #          2     11        13
 #              /    \      /
 #             9      5    7

 # Create binary tree
 root=node(3)
 l = root.left = node(6)
 r = root.right = node(8)
 r.right = node(13)
 r.right.left = node(7)
 l.left = node(2)
 l.right = node(11)
 l.right.left = node(9)
 l.right.right = node(5)

 print(lca(root, 2, 5).key)  # outputs '6'
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,48 @@
		# LCA - least common ancestor
		# The lowest common ancestor of two nodes n1 and n2 is the lowest node in tree that has both n1 and n2 as descendants.


		class node:
		def __init__(self,key):
		self.key=key
		self.left=None
		self.right=None

		def lca(root,n1,n2):
		if root is None:
		return None

		if root.key == n1 or root.key == n2:
		return root

		left = lca(root.left, n1, n2)
		right = lca(root.right, n1, n2)

		if left and right:
		return root

		return left if left else right


		# Consider the following binary tree

		# 3
		# / \
		# 6 8
		# / \ \
		# 2 11 13
		# / \ /
		# 9 5 7

		# Create binary tree
		root=node(3)
		l = root.left = node(6)
		r = root.right = node(8)
		r.right = node(13)
		r.right.left = node(7)
		l.left = node(2)
		l.right = node(11)
		l.right.left = node(9)
		l.right.right = node(5)

		print(lca(root, 2, 5).key) # outputs '6'