Given a Binary Tree with all unique values and two nodes value, n1 and n2. The task is to find the lowest common ancestor of the given two nodes. We may assume that either both n1 and n2 are present in the tree or none of them are present. 
LCA: It is the first common ancestor of both the nodes n1 and n2 from bottom of tree.
Example 1:
Input:
n1 = 2 , n2 = 3  
       1 
      / \ 
     2   3
Output: 1
Explanation:
LCA of 2 and 3 is 1.
Example 2:
Input:
n1 = 3 , n2 = 4
           5    
          /    
         2  
        / \  
       3   4
Output: 2
Explanation:
LCA of 3 and 4 is 2. 
Your Task:
You don't have to read, input, or print anything. Your task is to complete the function lca() that takes nodes, n1, and n2 as parameters and returns the LCA node as output. 
Expected Time Complexity:O(N).
Expected Auxiliary Space:O(Height of Tree).
Constraints:
1 ≤ Number of nodes ≤ 10^{5}
1 ≤ Data of a node ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3



'''

class Node:

    def __init__(self, value):

        self.left = None

        self.data = value

        self.right = None

'''



class Solution:

    #Function to return the lowest common ancestor in a Binary Tree.

    def lca(self,root, n1, n2):

        # Code here







Solutions:
class Solution:

	def lca(self, root, n1, n2):
		if root is None:
			return None
		if root.data == n1 or root.data == n2:
			return root
		in_left_tree = self.lca(root.left, n1, n2)
		in_right_tree = self.lca(root.right, n1, n2)
		if in_left_tree and in_right_tree:
			return root
		else:
			return in_left_tree or in_right_tree


class Solution:

	def lca(self, root, n1, n2):

		def LCAPath(root, path, tar):
			if root == None:
				return
			if root.data == tar:
				self.ans.append(path + [root.data])
			LCAPath(root.left, path + [root.data], tar)
			LCAPath(root.right, path + [root.data], tar)
		self.ans = []
		LCAPath(root, [], n1)
		ans1 = self.ans[0]
		self.ans = []
		LCAPath(root, [], n2)
		ans2 = self.ans[0]
		for i in range(min(len(ans1), len(ans2))):
			if ans1[i] == ans2[i]:
				val = ans1[i]
			else:
				return Node(val)
		return Node(val)


class Solution:

	def lca(self, root, n1, n2):

		def pathLCA(root, path, tar):
			if root == None:
				return
			if root.data == tar:
				self.ans.append(path + [root.data])
				return
			pathLCA(root.left, path + [root.data], tar)
			pathLCA(root.right, path + [root.data], tar)
		self.ans = []
		pathLCA(root, [], n1)
		ans1 = self.ans[0]
		self.ans = []
		pathLCA(root, [], n2)
		ans2 = self.ans[0]
		while ans1 and ans2:
			if ans1[-1] != ans2[-1]:
				if len(ans1) > len(ans2):
					ans1.pop()
				else:
					ans2.pop()
			else:
				return Node(ans1[-1])
		return Node(-1)


class Solution:

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

		def fun(root, n1, n2):
			if root is None:
				return None
			if root.data == n1 or root.data == n2:
				return root
			l = fun(root.left, n1, n2)
			r = fun(root.right, n1, n2)
			if l and r:
				return root
			elif l:
				return l
			else:
				return r
		return fun(root, n1, n2)


class Node:

	def __init__(self, value):
		self.left = None
		self.data = value
		self.right = None

class Solution:

	def lca(self, root, n1, n2):
		if root is None:
			return None
		if root.data == n1 or root.data == n2:
			return root
		left = self.lca(root.left, n1, n2)
		right = self.lca(root.right, n1, n2)
		if left is None:
			return right
		if right is None:
			return left
		return root


class Solution:

	def lca(self, root, n1, n2):

		def findlca(root, n1, n2, ans):
			if root is None:
				return 0
			leftval = findlca(root.left, n1, n2, ans)
			if leftval == 2:
				return leftval
			rightval = findlca(root.right, n1, n2, ans)
			if rightval == 2:
				return rightval
			foundval = leftval + rightval
			if root.data == n1 or root.data == n2:
				foundval += 1
			if foundval == 2:
				ans[0] = root
			return foundval
		ans = [None]
		findlca(root, n1, n2, ans)
		return ans[0]


class Solution:

	def lca(self, root, p, q):

		def answer(root):
			if root == None or root.data == p or root.data == q:
				return root
			lt = answer(root.left)
			rt = answer(root.right)
			if rt == None:
				return lt
			if lt == None:
				return rt
			else:
				return root
		return answer(root)


class Solution:

	def lca(self, root, n1, n2):
		data = [n1, n2]
		Node1 = Node(0)
		ans = [Node1]

		def F(root):
			if root == None:
				return False
			left = F(root.left)
			right = F(root.right)
			if left == True and right == True:
				ans.append(root)
				return True
			if root.data in data:
				data.remove(root.data)
				if len(data) == 0:
					ans.append(root)
				return True
			return left or right
		F(root)
		return ans[-1]


class Solution:

	def lca(self, root, n1, n2):
		if not root or root.data == n1 or root.data == n2:
			return root
		leftlca = self.lca(root.left, n1, n2)
		rightlca = self.lca(root.right, n1, n2)
		if leftlca and rightlca:
			return root
		return leftlca if leftlca else rightlca


class Solution:

	def lca(self, root, n1, n2):
		if not root:
			return None
		if root.data == n1 or root.data == n2:
			return root
		left = self.lca(root.left, n1, n2)
		right = self.lca(root.right, n1, n2)
		if left == None and right == None:
			return None
		if left == None and (not right == None):
			return right
		if not left == None and right == None:
			return left
		if not left == None and (not right == None):
			return root


class Solution:

	def lc(self, root, n1, n2):
		if root == None or root.data == n1 or root.data == n2:
			return root
		left = self.lc(root.left, n1, n2)
		right = self.lc(root.right, n1, n2)
		if left == None:
			return right
		if right == None:
			return left
		return root

	def lca(self, root, n1, n2):
		return self.lc(root, n1, n2)


class Solution:

	def lca(self, root, n1, n2):
		if not root or root.data == n1 or root.data == n2:
			return root
		left = self.lca(root.left, n1, n2)
		right = self.lca(root.right, n1, n2)
		if not left:
			return right
		elif not right:
			return left
		else:
			return root


class Node:

	def __init__(self, value):
		self.left = None
		self.data = value
		self.right = None

class Solution:

	def lca(self, root, n1, n2):
		if root == None:
			return Node(-1)
		if root.data == n1 or root.data == n2:
			return root
		c1 = self.lca(root.left, n1, n2)
		c2 = self.lca(root.right, n1, n2)
		if c1.data > 0 and c2.data > 0:
			return root
		elif c1.data > 0:
			return c1
		elif c2.data > 0:
			return c2
		else:
			return c1


class Solution:

	def lca(self, root, n1, n2):
		if root == None or root.data == n1 or root.data == n2:
			return root
		l = self.lca(root.left, n1, n2)
		r = self.lca(root.right, n1, n2)
		if l == None:
			return r
		elif r == None:
			return l
		else:
			return root


class Solution:

	def util(self, root, n1, n2):
		if root == None:
			return None
		if root.data == n1 or root.data == n2:
			return root
		l = self.util(root.left, n1, n2)
		r = self.util(root.right, n1, n2)
		if l != None and r != None:
			return root
		if l == None and r == None:
			return None
		if l != None:
			return l
		if r != None:
			return r

	def lca(self, root, n1, n2):
		return self.util(root, n1, n2)


class Node:

	def __init__(self, value):
		self.left = None
		self.data = value
		self.right = None

class Solution:

	def lca(self, root, n1, n2):
		if not root:
			return None
		if root.data == n1 or root.data == n2:
			return root
		left_lca = self.lca(root.left, n1, n2)
		right_lca = self.lca(root.right, n1, n2)
		if left_lca and right_lca:
			return root
		return left_lca if left_lca else right_lca


class Solution:

	def store(self, root, data=[]):
		if root is None:
			return
		self.dct[root.data] = data + [root.data]
		data = data + [root.data]
		self.store(root.left, data)
		self.store(root.right, data)

	def lca(self, root, n1, n2):
		self.dct = {}
		self.store(root)
		n1_list = self.dct[n1][::-1]
		n2_list = self.dct[n2][::-1]
		for itr in n1_list:
			if itr in n2_list:
				return Node(itr)


class Solution:

	def solve(self, root, n1, n2):
		if root == None:
			return None
		if root.data == n1 or root.data == n2:
			return root
		left = self.solve(root.left, n1, n2)
		right = self.solve(root.right, n1, n2)
		if left != None and right != None:
			return root
		elif left == None and right != None:
			return right
		elif left != None and right == None:
			return left
		else:
			return None

	def lca(self, root, n1, n2):
		return self.solve(root, n1, n2)


class Solution:

	def findpath(self, root, path, x):
		if root is None:
			return False
		path.append(root)
		if root.data == x:
			return True
		if self.findpath(root.left, path, x) or self.findpath(root.right, path, x):
			return True
		path.pop()
		return False

	def lca(self, root, n1, n2):
		(p1, p2) = ([], [])
		if not self.findpath(root, p1, n1) or not self.findpath(root, p2, n2):
			return None
		i = 0
		while i < len(p1) and i < len(p2):
			if p1[i] != p2[i]:
				break
			i += 1
		return p1[i - 1]


class Solution:

	def lca(self, root, n1, n2):
		if root is None or root.data == n1 or root.data == n2:
			return root
		left_lca = self.lca(root.left, n1, n2)
		right_lca = self.lca(root.right, n1, n2)
		if left_lca and right_lca:
			return root
		if left_lca is None:
			return right_lca
		if right_lca is None:
			return left_lca


class Solution:

	def lca(self, root, n1, n2):
		if not root:
			return None
		if root.data == n1 or root.data == n2:
			return root
		else:
			leftLCA = self.lca(root.left, n1, n2)
			rightLCA = self.lca(root.right, n1, n2)
			if leftLCA and rightLCA:
				return root
			elif leftLCA:
				return leftLCA
			elif rightLCA:
				return rightLCA
			else:
				return None


class Solution:

	def lca(self, root, n1, n2):

		def findNode(root, l, x):
			if root is None:
				return False
			l.append(root)
			if root.data == x:
				return True
			if findNode(root.left, l, x) or findNode(root.right, l, x):
				return True
			l.pop()
			return False
		l1 = []
		findNode(root, l1, n1)
		l2 = []
		findNode(root, l2, n2)
		i = 0
		j = 0
		x = None
		while i < len(l1) and j < len(l2):
			if l1[i].data == l2[j].data:
				x = l1[i]
				i += 1
				j += 1
			else:
				break
		return x


class Solution:

	def lca(self, root, n1, n2):

		def commonAncestor(root, k1, k2):
			if root != None:
				(l1, l2, ld) = commonAncestor(root.left, k1, k2)
				(r1, r2, rd) = commonAncestor(root.right, k1, k2)
				Key1_found = True if root.data == k1 else l1 or r1
				Key2_found = True if root.data == k2 else l2 or r2
				key = ld if ld != None else rd
				if key == None and Key1_found and Key2_found:
					key = root
				return (Key1_found, Key2_found, key)
			return (False, False, None)
		(_, _, v) = commonAncestor(root, n1, n2)
		return v


def roottoleaf(root, node, path):
	if root == None:
		return False
	path.append(root)
	if root.data == node:
		return True
	if roottoleaf(root.left, node, path) or roottoleaf(root.right, node, path):
		return True
	path.pop(-1)
	return False

class Solution:

	def lca(self, root, n1, n2):
		path1 = []
		path2 = []
		roottoleaf(root, n1, path1)
		roottoleaf(root, n2, path2)
		if len(path1) == 0 or len(path2) == 0:
			return -1
		i = 0
		while i < len(path1) and i < len(path2):
			if path1[i] != path2[i]:
				break
			i += 1
		return path1[i - 1]


class Solution:

	def lca(self, root, n1, n2):
		if root == None:
			return None
		if root.data == n1 or root.data == n2:
			return root
		a = self.lca(root.left, n1, n2)
		b = self.lca(root.right, n1, n2)
		if a != None and b != None:
			return root
		if a != None and b == None:
			return a
		if a == None and b != None:
			return b


class Solution:

	def rec_sol(self, root, n1, n2, ans):
		if root == None:
			return -1
		left_ans = self.rec_sol(root.left, n1, n2, ans)
		right_ans = self.rec_sol(root.right, n1, n2, ans)
		if root.data == n1 or root.data == n2:
			if left_ans == 1 or right_ans == 1:
				ans.append(root)
			return 1
		if left_ans == 1 and right_ans == 1:
			ans.append(root)
			return 1
		elif left_ans == 1 or right_ans == 1:
			return 1
		return -1

	def lca(self, root, n1, n2):
		ans = []
		self.rec_sol(root, n1, n2, ans)
		if len(ans) == 0:
			return -1
		return ans[0]


class Solution:

	def findNode(self, root, n1, n2):
		if not root:
			return None
		if root.data == n1 or root.data == n2:
			return root
		leftAns = self.findNode(root.left, n1, n2)
		rightAns = self.findNode(root.right, n1, n2)
		if leftAns != None and rightAns != None:
			return root
		if leftAns == None and rightAns != None:
			return rightAns
		if leftAns != None and rightAns == None:
			return leftAns
		return None

	def lca(self, root, n1, n2):
		ans = self.findNode(root, n1, n2)
		return ans


def find_lca_using_recursion(value_1, value_2, node):
	if node is None:
		return (False, False, None)
	left = find_lca_using_recursion(value_1, value_2, node.left)
	right = find_lca_using_recursion(value_1, value_2, node.right)
	found_1 = value_1 == node.data or left[0] or right[0]
	found_2 = value_2 == node.data or left[1] or right[1]
	if found_1 and found_2:
		ans = left[2] or right[2] or node
	else:
		ans = None
	return (found_1, found_2, ans)

class Solution:

	def lca(self, root, n1, n2):
		lca = find_lca_using_recursion(n1, n2, root)
		return lca[2]


class Solution:

	def lca(self, root, n1, n2):

		def solve(root):
			if not root:
				return (root, False)
			if root.data == n1 or root.data == n2:
				return (root, True)
			if root:
				(lr, ls) = solve(root.left)
				(rr, rs) = solve(root.right)
				if ls and rs:
					return (root, True)
				if ls:
					return (lr, True)
				if rs:
					return (rr, True)
				return (root, False)
		(ar, ast) = solve(root)
		return ar


class Solution:

	def lca(self, root, n1, n2):
		if root is None:
			return None
		if root.data == n1 or root.data == n2:
			return root
		left = self.lca(root.left, n1, n2)
		right = self.lca(root.right, n1, n2)
		if left and right:
			return root
		elif left:
			return left
		else:
			return right
		return Node(-1)


class Solution:

	def lca(self, root, n1, n2):

		def h(root, n1, n2):
			if root == None:
				return root
			if root.data == n1 or root.data == n2:
				return root
			l = h(root.left, n1, n2)
			r = h(root.right, n1, n2)
			if not l:
				return r
			if not r:
				return l
			return root
		return h(root, n1, n2)


def findLCA(root, n1, n2, ans, curr):
	if root == None:
		return
	if root.data == n1:
		ans[0] = curr[0]
	if root.data == n2:
		ans[1] = curr[0]
	if ans[0] != 'N' and ans[1] != 'N':
		return
	if root.left:
		findLCA(root.left, n1, n2, ans, [curr[0] + '0'])
	if root.right:
		findLCA(root.right, n1, n2, ans, [curr[0] + '1'])

class Solution:

	def lca(self, root, n1, n2):
		ans = ['N', 'N']
		st = ''
		curr = [st]
		findLCA(root, n1, n2, ans, curr)
		(r1, r2) = ans
		n = min(len(r1), len(r2))
		i = 0
		while i < n:
			if r1[i] == r2[i]:
				i += 1
			else:
				break
		str = r1[:i]
		for s in str:
			if s == '1':
				root = root.right
			else:
				root = root.left
		return root


class Solution:

	def lca(self, root, n1, n2):
		ans = []

		def dfs(root, n, ans=[]):
			ans.append(root)
			if root.data == n:
				return True
			if root.left:
				if dfs(root.left, n, ans):
					return True
			if root.right:
				if dfs(root.right, n, ans):
					return True
			ans.pop()
		dfs(root, n1, ans)
		x1 = ans
		ans = []
		dfs(root, n2, ans)
		x2 = ans
		l1 = len(x1)
		l2 = len(x2)
		if l1 > l2:
			for i in range(l2):
				if x1[i] != x2[i]:
					return x1[i - 1]
			return x2[-1]
		else:
			for i in range(l1):
				if x1[i] != x2[i]:
					return x1[i - 1]
			return x1[-1]


def find_ancestors(root, n, original_ancestors):
	ancestors = original_ancestors.copy()
	if root == None:
		return None
	elif root.data == n:
		ancestors.append(root)
		return ancestors
	ancestors.append(root)
	leftfound = find_ancestors(root.left, n, ancestors)
	if leftfound != None:
		return leftfound
	else:
		rightfound = find_ancestors(root.right, n, ancestors)
		if rightfound != None:
			return rightfound
	return None

class Solution:

	def lca(self, root, n1, n2):
		n1p = []
		n2p = []
		node = root
		n1p = find_ancestors(root, n1, [])
		n2p = find_ancestors(root, n2, [])
		matched = None
		for n1 in n1p:
			for n2 in n2p:
				if n1 == n2:
					matched = n1
		return matched


class Solution:

	def lca(self, root, n1, n2):
		v = [False, False]
		lca = self.findLCA(root, n1, n2, v)
		if v[0] and v[1] or (v[0] and self.find(lca, n2)) or (v[1] and self.find(lca, n1)):
			return lca
		return None

	def find(self, root, k):
		if root is None:
			return False
		return root.data == k or self.find(root.left, k) or self.find(root.right, k)

	def findLCA(self, root, n1, n2, v):
		if not root:
			return None
		if root.data == n1:
			v[0] = True
			return root
		if root.data == n2:
			v[1] = True
			return root
		leftLCA = self.findLCA(root.left, n1, n2, v)
		rightLCA = self.findLCA(root.right, n1, n2, v)
		if leftLCA and rightLCA:
			return root
		return leftLCA if leftLCA else rightLCA


class Solution:

	def lca(self, root, n1, n2):
		if root is None:
			return None
		if root.data == n1 or root.data == n2:
			return root
		l = self.lca(root.left, n1, n2)
		r = self.lca(root.right, n1, n2)
		if l and r:
			return root
		return l if l is not None else r