Lowest Common Ancestor | Binary Search Tree

First before we looking into the problem, let's first understand the application why is this helpful?

Real world Example

Course Prerequisites: Finding common prerequisite courses that students need to complete before taking advanced courses

Social Networks

In social networks like Facebook or LinkedIn, connections can form a graph or tree structure when narrowed to specific contexts. Finding the LCA can help in:

• Finding mutual connections: If two users share a mutual connection or group, the LCA in a tree can identify their closest shared connection or network.
• Influencer Analysis: If you treat user influence as a tree, the LCA can identify the closest influencer who impacts two individuals.

Given a binary search tree (BST) where all node values are unique, and two nodes from the tree p and q, return the lowest common ancestor (LCA) of the two nodes.

The lowest common ancestor between two nodes p and q is the lowest node in a tree T such that both p and q as descendants. The ancestor is allowed to be a descendant of itself.

Example 1:

Input: root = [5,3,8,1,4,7,9,null,2], p = 3, q = 8

Output: 5

Example 2:

Input: root = [5,3,8,1,4,7,9,null,2], p = 3, q = 4

Output: 3

Explanation: The LCA of nodes 3 and 4 is 3, since a node can be a descendant of itself.

A recursive solution is generally cleaner and more intuitive for finding the Lowest Common Ancestor (LCA). Here's how it works:

1. If the root is null, return null.
2. If the root is equal to p or q, return the root.
3. Recursively search for p and q in the left and right subtrees.
4. If both left and right subtrees return non-null nodes, the current node is the LCA.
5. Otherwise, return the non-null node.

When traversing the binary tree, the LCA of two nodes (p and q) is the node where:

• One of the nodes (p or q) is found in the left subtree, and
• The other node is found in the right subtree.

If both the left and right subtrees return a non-null value, it means that one node is located in the left subtree and the other in the right subtree.

Thus, the current root is their lowest common ancestor.

If we are searching Recursively:

What is the base case?

1. If we reach null anytime on traversing, that' means we've reached a leaf node and didn't find either p or q node in this branch, so return null
2. If node === p or q, return that node node

PseudoCode:

1. If we reach at the leaf node and didn't find our match, we return null
2. if we reach a node, where this node.val === p.val || q.val then we return this node
3. Recursive:
4. At the current node, we recursively check its left and right subtrees to find p and q.
5. IF there is a match: If both the left and right subtrees return a non-null value, it means p is in one subtree, and q is in the other subtree. This makes the current node the LCA, so we return the current node.
6. If leftTree === null , no match in the left subtree and rightTree === null i.e no match in the right subtree, there are no relevant nodes in this branch.
7. The function returns null to the parent node in the recursion stack.

function lca(node, p, q){
 if(!node) return null
 if(node.val === p.val || node.val === q.val) return node
 
 const leftTree  = this.lca(node.left, p, q)
 const rightTree = this.lca(node.right, p, q)

 if(leftTree !== null && rightTree!== null) return node
 
 return leftTree !== null? leftTree : rightTree
}

lowestCommonAncestor(root, p, q) {
if (!root) return null

// if root val is gtr than both node go left to find smlr val

if (p.val < root.val && q.val < root.val) {
return  this.lowestCommonAncestor(root.left, p, q)

// if root val is smlr than both the node than go right to find bigger val
 
} else if (root.val < p.val && root.val < q.val) {
  return this.lowestCommonAncestor(root.right, p, q)
 } else return root
}