[[Binary trees and Binary search trees]]

Problem

Same problem as [[LCA in a binary tree]] , but this time you are guaranteed that the input tree is a valid Binary Search Tree with distinct keys.

Brainstorming

The added advantage we have now is that the tree is guaranteed to be a binary search tree. A binary search tree has a very significant property

node.left.data <= node.data <= node.right.data

so in this case we can look at p and q and decide using this property where to look for our LCA.

in the standard problem the idea is to go all the way to the bottom and try to find a solution from there. in this case we can avoid that , lets take an example to pen out the algorithm

	20
   /  \
 10   30
/ \   / \
5 15 25 35

p = 5
q = 15 

lets take this example and try to see how it goes

1. we start at 20 we check if 5 is less than 20 yes , it means p is definitely in the left side of the tree
2. we check for 15 yes even that is less that means its guaranteed our LCA is in the left side of the tree we go left
3. we check 10 is 5 less than 10 yes ! so p is in the left side of the tree
4. we check 15 is that less than 10 no !! it means means q is on the right side of the tree
5. is node.left.data = 5 and node.right.data = 10 if yes then the current node is LCA return it (this can be a base case)

lets try with p =15 and q = 25 (p and q in different subtrees)

1. we start and find p is less than 20 and q is greater than 20 it means by default of the property of the bst the lca is 20

so essentially 3 cases come up that we need to check

• case 1: both p and q are smaller than node.data it means the lca is definitely on the left subtree hence traverse left
• case 2: both p and q are greater than node.data it means the lca is definitely on the right subtree hence traverse right
• case 3 : if p is smaller than node.data and q is greater than node.data it means by the property of BST node is the LCA

class TreeNode:
	def __init__(self, val=None, left=None, right=None):
		self.val = val
		self.left = left
		self.right = right
	
def lca_in_bst(node:TreeNode, p, q):
	# base case 1 end of tree 
	if node is None:
		return None:
	

		return node
	
	if node.data > p and node.data > q:
		return lca_in_bst(node.left, p, q)
	elif node.data < p and node.data < q:
		return lca_in_bst(node.right, p, q)
	else : # # base case 2 	if (node.data > p or node.data < q) or (node.data > q or node.data < p):
		# If neither of the above is true, it means we have a split,
		# or the current node is one of p or q.
		# Therefore, this currentNode is the LCA.
		return node 
		
	

Tail recursion

Recursion needs to maintain a call stack that can be as big as the height of the tree hence any recursive based tree solution as a space complexity of O(h)

we can use pointer approach and reduce this significantly

the key idea is case 1 and case 2 , if we hit any of these we know by default where we have to look (left sub tree or right subtree) hence we don’t really need to use tree traversals

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

def lca_bst(node:TreeNode, p,q):
	
	while node:
		if node.data > q and node.data > q:
			node = node.left # go left
		elif node.data < p and node.data < q:
			node = node.right # go right
		else:
			return node # there is a guranteed split hence current node is the LCA
	
	return None # this becomes the base case if the tree is empty