Given a Binary Search Tree (with all values unique) and two node values. Find the Lowest Common Ancestors of the two nodes in the BST.
Example 1:
Input:
              5
            /   \
          4      6
         /        \
        3          7
                    \
                     8
n1 = 7, n2 = 8
Output: 7
Example 2:
Input:
     2
   /   \
  1     3
n1 = 1, n2 = 3
Output: 2
Your Task:
You don't need to read input or print anything. Your task is to complete the function LCA() which takes the root Node of the BST and two integer values n1 and n2 as inputs and returns the Lowest Common Ancestor of the Nodes with values n1 and n2 in the given BST. 
Expected Time Complexity: O(Height of the BST).
Expected Auxiliary Space: O(Height of the BST).
Constraints:
1 <= N <= 10^{4}

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Range queries

Starter code: #User function Template for python3





#Function to find the lowest common ancestor in a BST. 

def LCA(root, n1, n2):

    #code here.

Solutions:
def LCA(root, n1, n2):
	value = root
	list1 = [root.data]
	list2 = [root.data]
	while value.data != n1:
		if value.data > n1:
			value = value.left
		elif value.data < n1:
			value = value.right
		list1.append(value.data)
	list1.append(99999)
	value = root
	while value.data != n2:
		if value.data > n2:
			value = value.left
		elif value.data < n2:
			value = value.right
		list2.append(value.data)
	list2.append(88888)
	i = 0
	while list1[i] == list2[i]:
		i += 1
	result = list1[i - 1]
	value = root
	while value.data != result:
		if value.data > result:
			value = value.left
		elif value.data < result:
			value = value.right
	return value


def LCA(root, n1, n2):

	def lca(root, n1, n2):
		if n1 > root.data and n2 > root.data:
			return lca(root.right, n1, n2)
		elif n1 < root.data and n2 < root.data:
			return lca(root.left, n1, n2)
		elif (n1 > root.data and n2 < root.data) and (n1 < root.data and n2 > root.data):
			return root
		return root
	return lca(root, n1, n2)


def LCA(root, n1, n2):
	if root is None:
		return None
	if root.data > n1 and root.data > n2:
		return LCA(root.left, n1, n2)
	elif root.data < n1 and root.data < n2:
		return LCA(root.right, n1, n2)
	return root


def LCA(root, n1, n2):
	while root:
		if root.data > n1 and root.data > n2:
			root = root.left
		elif root.data < n1 and root.data < n2:
			root = root.right
		else:
			break
	return root


def LCA(r, n1, n2):
	while r:
		if r.data == n1 or r.data == n2:
			return r
		if n1 < r.data and n2 > r.data or (n1 > r.data and n2 < r.data):
			return r
		if n1 < r.data and n2 < r.data:
			r = r.left
		if n1 > r.data and n2 > r.data:
			r = r.right


def get_lca(p, data1, data2):
	if p is None:
		return None
	elif p.data == data1 or p.data == data2:
		return p
	elif data1 == data2:
		q = Node(data1)
		return q
	elif p.data > data1 and p.data > data2:
		p = p.left
		return get_lca(p, data1, data2)
	elif p.data < data1 and p.data < data2:
		p = p.right
		return get_lca(p, data1, data2)
	elif p.data > data1 and p.data < data2 or (p.data < data1 and p.data > data2):
		return p

def LCA(root, n1, n2):
	if root:
		return get_lca(root, n1, n2)
	else:
		return -1


def LCA(root, n1, n2):
	if n1 > n2:
		(n1, n2) = (n2, n1)

	def recursive(root):
		if root is None:
			return None
		if n1 <= root.data <= n2:
			return root
		elif n2 < root.data:
			return recursive(root.left)
		else:
			return recursive(root.right)
	return recursive(root)


def LCA(root, n1, n2):
	small = min(n1, n2)
	large = max(n1, n2)
	while root:
		if root.data < small:
			root = root.right
		elif root.data > large:
			root = root.left
		else:
			return root
	return None


def LCA(root, n1, n2):
	out = [root]

	def traverse(root):
		if not root:
			return
		if n1 > root.data and n2 > root.data:
			traverse(root.right)
		elif n1 < root.data and n2 < root.data:
			traverse(root.left)
		else:
			out[0] = root
			return
	traverse(root)
	return out[0]


preorder = None

def LCA(root, n1, n2):
	global preorder
	if root.data >= n1 and root.data <= n2 or (root.data <= n1 and root.data >= n2):
		return root
	if root.data > n1 and root.data > n2:
		preorder = LCA(root.left, n1, n2)
	if root.data < n1 and root.data < n2:
		preorder = LCA(root.right, n1, n2)
	return preorder


def LCA(root, n1, n2):

	def findpath(root, n):
		result = []
		if not root:
			return result
		while root:
			result.append(root)
			if root.data == n:
				return result
			elif root.data < n:
				root = root.right
			else:
				root = root.left
	leftList = findpath(root, n1)
	rightList = findpath(root, n2)
	leftiter = iter(leftList)
	rightiter = iter(rightList)
	left = next(leftiter, None)
	right = next(rightiter, None)
	ans = root
	while left and right:
		if left.data == right.data:
			ans = left
		else:
			return ans
		left = next(leftiter, None)
		right = next(rightiter, None)
	if left:
		return rightList[-1]
	elif right:
		return leftList[-1]
	else:
		return root


def LCA(root, n1, n2):
	if not root:
		return 0
	if root.data < n1 and root.data < n2:
		return LCA(root.right, n1, n2)
	if root.data > n1 and root.data > n2:
		return LCA(root.left, n1, n2)
	return root


def LCA(root, n1, n2):
	if root is None:
		return None
	if root.data == n1 or root.data == 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


def LCA(root, n1, n2):

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


ans = 0

def gen(root, n1, n2):
	global ans
	if root.data == n1 or root.data == n2:
		ans = root
		return root
	if root.data > n1 and root.data < n2:
		ans = root
		return root
	if root.data < n1 and root.data > n2:
		ans = root
		return root
	if root.left != None and ans == 0:
		gen(root.left, n1, n2)
	if root.right != None and ans == 0:
		gen(root.right, n1, n2)

def LCA(root, n1, n2):
	global ans
	ans = 0
	a = gen(root, n1, n2)
	return ans


def LCA(root, n1, n2):
	p = Node(n1)
	q = Node(n2)
	while root != None:
		if root.data < p.data and root.data < q.data:
			root = root.right
		elif root.data > p.data and root.data > q.data:
			root = root.left
		else:
			return root


def LCA(root, n1, n2):
	node = root
	d = []
	while node != None:
		d.append(node)
		if node.data == n1:
			break
		elif node.data < n1:
			node = node.right
		elif node.data > n1:
			node = node.left
	if n1 == n2:
		return node
	node = root
	while node != None:
		prev = node
		if node.data == n2:
			return node
			break
		elif node.data < n2:
			node = node.right
		elif node.data > n2:
			node = node.left
		if node not in d:
			return prev


def LCA(root, n1, n2):
	_min = min(n1, n2)
	_max = max(n1, n2)
	if _min < root.data and _max > root.data or _min == root.data or _max == root.data:
		return root
	elif _min < root.data:
		return LCA(root.left, n1, n2)
	else:
		return LCA(root.right, n1, n2)


def LCA(root, n1, n2):
	if root is None:
		return None
	if root.data == n1 or root.data == n2:
		return root
	l = LCA(root.left, n1, n2)
	r = LCA(root.right, n1, n2)
	return root if all([l, r]) else l or r or None


def LCA(root, n1, n2):

	def traverse(root, n1, n2):
		if root is None or n1 < root.data < n2 or root.data == n1 or (root.data == n2):
			return root
		if n1 > root.data and n2 > root.data:
			return traverse(root.right, n1, n2)
		if n1 < root.data and n2 < root.data:
			return traverse(root.left, n1, n2)
	return traverse(root, min(n1, n2), max(n1, n2)) or root


def LCA(root, n1, n2):

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


def LCA(root, n1, n2):
	if root == None:
		return -1
	if root.data > n1 and root.data > n2:
		return LCA(root.left, n1, n2)
	if root.data < n1 and root.data < n2:
		return LCA(root.right, n1, n2)
	return root


def LCA(root, n1, n2):
	if root.data < min(n1, n2):
		return LCA(root.right, n1, n2)
	elif root.data > max(n1, n2):
		return LCA(root.left, n1, n2)
	return root


def LCA(root, n1, n2):
	if not root:
		return None
	if root.data in [n1, n2]:
		return root
	(l, r) = (LCA(x, n1, n2) for x in [root.left, root.right])
	return root if all([l, r]) else l or r or None


def LCA(root, n1, n2):
	if root is None:
		return None
	curr = root.data
	if curr < n1 and curr < n2:
		return LCA(root.right, n1, n2)
	if curr > n1 and curr > n2:
		return LCA(root.left, n1, n2)
	return root

def LCA(root, n1, n2):
	if root is None:
		return None
	while root:
		curr = root.data
		if curr > n1 and curr > n2:
			root = root.left
		elif curr < n1 and curr < n2:
			root = root.right
		else:
			return root


def find_path(root, path, n1):
	if not root:
		return False
	path.append(root)
	if root.data == n1:
		return True
	if find_path(root.left, path, n1) or find_path(root.right, path, n1):
		return True
	path.pop()
	return False

def LCA(root, n1, n2):
	path_1 = []
	find_path(root, path_1, n1)
	path_2 = []
	find_path(root, path_2, n2)
	ans = root
	if len(path_1) < len(path_2):
		(path_1, path_2) = (path_2, path_1)
	for i in range(len(path_2)):
		if path_1[i] != path_2[i]:
			return ans
		ans = path_1[i]
	return ans


def LCA(root, n1, n2):
	if root:
		if root.data == n1 or root.data == n2:
			return root
		if nodeIn(root.left, n1) and nodeIn(root.right, n2) or (nodeIn(root.left, n2) and nodeIn(root.right, n1)):
			return root
		left = LCA(root.left, n1, n2)
		if left is None:
			return LCA(root.right, n1, n2)
		return left

def nodeIn(node, n):
	if node is None:
		return False
	if node.data == n:
		return True
	return nodeIn(node.left, n) or nodeIn(node.right, n)


def TravForMeDaddy(root, value, li):
	if root:
		if root.data == value:
			li.append(root)
			return
		elif root.data > value:
			li.append(root)
			TravForMeDaddy(root.left, value, li)
		elif root.data < value:
			li.append(root)
			TravForMeDaddy(root.right, value, li)

def LCA(root, n1, n2):
	if root:
		n1prevlist = []
		n2prevlist = []
		TravForMeDaddy(root, n1, n1prevlist)
		TravForMeDaddy(root, n2, n2prevlist)
		for i in n1prevlist[::-1]:
			if i in n2prevlist:
				return i
	else:
		return -1


def LCA(root, n1, n2):

	def fun(root, a, b):
		if root == None or root.data == a or root.data == b:
			return root
		lh = fun(root.left, a, b)
		rh = fun(root.right, a, b)
		if lh != None and rh != None:
			return root
		elif rh != None:
			return rh
		else:
			return lh
	x = fun(root, n1, n2)
	return x


def LCA(root, n1, n2):
	if root:
		if root.data < n1 and root.data < n2:
			return LCA(root.right, n1, n2)
		if root.data > n1 and root.data > n2:
			return LCA(root.left, n1, n2)
		return root


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

def LCA(root, n1, n2):
	return func(root, n1, n2)


def LCA(root, n1, n2):
	return L(root, n1, n2)

def L(root, n1, n2):
	if not root or root.data == n1 or root.data == n2:
		return root
	lh = L(root.left, n1, n2)
	rh = L(root.right, n1, n2)
	if not rh:
		return lh
	if not lh:
		return rh
	else:
		return root


def diver(root, n1, n2):
	if n1 > root.data and n2 > root.data:
		return diver(root.right, n1, n2)
	elif n1 < root.data and n2 < root.data:
		return diver(root.left, n1, n2)
	else:
		return root

def LCA(root, n1, n2):
	return diver(root, n1, n2)


def LCA(root, n1, n2):
	if root is None:
		return None
	if root.data == n1 or root.data == n2:
		return root
	lans = LCA(root.left, n1, n2)
	rans = LCA(root.right, n1, n2)
	if lans != None and rans != None:
		return root
	if lans != None and rans == None:
		return lans
	if lans == None and rans != None:
		return rans


def LCA(root, n1, n2):
	if n1 <= n2:
		return get_lca_util(root, n1, n2)
	else:
		return get_lca_util(root, n2, n1)

def get_lca_util(root, start, end):
	if root is None:
		return None
	if start <= root.data <= end:
		return root
	elif end < root.data:
		return get_lca_util(root.left, start, end)
	else:
		return get_lca_util(root.right, start, end)


def helper(root, n1, n2):
	if not root:
		return (False, None)
	(l, l_v) = helper(root.left, n1, n2)
	(r, r_v) = helper(root.right, n1, n2)
	if l_v:
		return (True, l_v)
	if r_v:
		return (True, r_v)
	if l and r:
		return (True, root)
	elif l and (root.data == n1 or root.data == n2):
		return (True, root)
	elif r and (root.data == n1 or root.data == n2):
		return (True, root)
	if root.data == n1 or root.data == n2:
		return (True, None)
	return (l or r, l_v if l_v else r_v)

def LCA(root, n1, n2, ret=[]):
	r = helper(root, n1, n2)
	return r[1]


def LCA(root, n1, n2):
	if n1 > n2:
		(n1, n2) = (n2, n1)

	def findlca(root, n1, n2):
		if root == None:
			return None
		if root.data == n1 or root.data == n2:
			return root
		if n1 <= root.data and n2 > root.data:
			return root
		if n1 > root.data:
			return findlca(root.right, n1, n2)
		if n1 < root.data:
			return findlca(root.left, n1, n2)
	return findlca(root, n1, n2)


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

def LCA(root, n1, n2):
	global d
	d = {}
	arr = []
	store(root, arr)
	b1 = d[n1][::-1]
	b2 = d[n2][::-1]
	for itr in b1:
		if itr in b2:
			return Node(itr)


def LCA(root, n1, n2):

	def lca(root, n1, n2):
		if not root:
			return None
		if n1 < root.data and n2 < root.data:
			return lca(root.left, n1, n2)
		elif n1 > root.data and n2 > root.data:
			return lca(root.right, n1, n2)
		else:
			return root
	return lca(root, n1, n2)


def LCA(root, n1, n2):

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


def LCA(root, n1, n2):
	if root == None:
		return root
	if root.data == n1 or root.data == n2:
		return root
	leftLCA = LCA(root.left, n1, n2)
	rightLCA = LCA(root.right, n1, n2)
	if leftLCA != None and rightLCA != None:
		return root
	else:
		return leftLCA if rightLCA == None else rightLCA


def LCA(root, n1, n2):
	from bisect import bisect_left

	def getTraverse(nodes, l):
		next_nodes = []
		for node in nodes:
			if not node or node == 'N':
				l.append('N')
				next_nodes += ['N', 'N']
			else:
				l.append(node.data)
				next_nodes += [node.left, node.right]
		if len(set(next_nodes)) > 1:
			getTraverse(next_nodes, l)

	def getNode(node, val):
		if node.data == val:
			return node
		elif node.data > val:
			return getNode(node.left, val)
		else:
			return getNode(node.right, val)
	l = []
	getTraverse([root], l)
	idx1 = l.index(n1)
	idx2 = l.index(n2)
	while idx1 != idx2:
		if idx1 > idx2:
			idx1 = (idx1 + 1) // 2 - 1
		else:
			idx2 = (idx2 + 1) // 2 - 1
	return getNode(root, l[idx1])


def f(root, n, li):
	if root == None:
		return li
	li.append(root)
	if root.data > n:
		li = f(root.left, n, li)
	elif root.data < n:
		li = f(root.right, n, li)
	return li

def LCA(root, n1, n2):
	l1 = []
	l2 = []
	l1 = f(root, n1, l1)
	l2 = f(root, n2, l2)
	i = 0
	a = 0
	while i < len(l1) and i < len(l2):
		if l1[i].data == l2[i].data:
			a = l1[i]
		i += 1
	return a


def find_path(root, n1):
	if not root:
		return None
	if root.data == n1:
		return [root]
	left = find_path(root.left, n1)
	if left:
		return [root] + left
	right = find_path(root.right, n1)
	if right:
		return [root] + right
	return None

def LCA(root, n1, n2):
	n1_path = find_path(root, n1)
	n2_path = find_path(root, n2)
	if len(n1_path) < len(n2_path):
		(n1_path, n2_path) = (n2_path, n1_path)
	n2_path = set(n2_path)
	for i in reversed(range(len(n1_path))):
		if n1_path[i] in n2_path:
			return n1_path[i]
	return None


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