[[Binary trees and Binary search trees]]

Problem

you are given the root of a binary tree and two nodes, p and q, that are in the tree. Find the node that is the “lowest” (deepest) common ancestor of both p and q. The node itself can be an ancestor.

Example 1

  A
 / \
 B C
/ / \
D E F

• LCA of D and E: The path to D is A -> B -> D. The path to E is A -> C -> E. The first (and only) common node in those paths is A.

• LCA of E and F: The path to E is A -> C -> E. The path to F is A -> C -> F. The lowest common ancestor is C.

Brainstorming

What is an LCA? as the definition states its the lowest ( starting) from the top node which hosts our nodes p and q on the left and the right side of it. It may or may not be the node that directly hosts them. As given in the example problem. But how do we find them.

Suppose we have to trace it by hand for the below tree how would that algo look?

   A
  / \
 B   C
/ \  / \
F E  D  G

lets see if p is B and q is C we start at root A we check if B and C are on the either side of the node it is and then if they are there then we can return A as the common LCA . but this doesn’t work well for cases where the current node is not directly hosting our P and Q .

So instead of doing top down lets do a bottom up approach where we traverse a tree all the way from a leaf to the top take the case of B and C if do post order traversal then

1. We will first go left and all the way down i.e till F
2. We can check if F is B or C its not. we return Nothing
3. Then we go right i.e to E is E B or C , its not we return Nothing.
4. then we check if B is B or C it is !! we return it Current_node
5. Now we are at A and from left we have found 1 node that is B
6. we go right and then left i.e D is C or B no we return nothing
7. We go right to G is it B or C no we return nothing
8. then we check for C is it B or C yes !! we return it Current_node
9. now we have a result from right and left at A level so the check at the current node is simple
   1. if both right and left are not none that means the current node is the LCA ( since we have gone bottom to top hence the first node that satisfies this is by default the lowest)
   2. if in case we find either left or right we just return that
10. This way we are traversing a tree in reverse order and storing the result

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

def lca_binary_tree(node:TreeNode, p, q):
	
	# Base case 2
	if node is None:
		return None
	
	# Base case 2 if the current node is a value we are trying to find
	if node.data == p or node.data == q:
		return node
	
	# traversal
	left = lca_binary_tree(node.left, p,q)
	right = lca_binary_tree(node.right, p,q)
	
	if left and right:
		return node # we have found our LCA
	
	return left or right # return either of the node we find