Lowest Common Ancestor (LCA) šŸŽÆ

beginner
5 min

Lowest Common Ancestor (LCA) šŸŽÆ

Welcome to your journey into the fascinating world of Data Structures and Algorithms! Today, we'll dive deep into understanding the Lowest Common Ancestor (LCA) concept. This is a crucial topic in graph theory, and it plays a significant role in various real-world applications.

What is the Lowest Common Ancestor (LCA)? šŸ“

In a tree data structure, the Lowest Common Ancestor (LCA) of two nodes is the closest common ancestor that has both nodes as descendants. It's the node that is the most recent common ancestor of the two nodes in the tree.

Let's break it down with a simple example:

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

In this tree, if we consider nodes E and G, their LCA would be node C because it's the deepest node that is a common ancestor for both E and G.

Why is LCA Important? šŸ’”

The LCA is essential in various real-world applications, such as:

  1. Social Networks: To find common friends between users in a network.
  2. Databases: To optimize queries by reducing the search space.
  3. Compiler Optimization: To analyze the structure of parse trees.

LCA Algorithms šŸ“

There are several algorithms to find the LCA in a tree, but today, we'll focus on the most common ones:

  1. Depth-First Search (DFS)
  2. Binary Lifted Bit Operators

Depth-First Search (DFS) šŸ“

DFS is a popular algorithm for finding the LCA. Let's create a simple implementation:

python
class Node: def __init__(self, key): self.key = key self.left = None self.right = None def lca(root, n1, n2): if root is None: return None # If both nodes are present in the left subtree, then LCA is in the left subtree if root.left and (root.left.key == n1 or root.left.key == n2): return lca(root.left, n1, n2) # If both nodes are present in the right subtree, then LCA is in the right subtree if root.right and (root.right.key == n1 or root.right.key == n2): return lca(root.right, n1, n2) # If both nodes are equal to the root, then the root is the LCA if root.key == n1 or root.key == n2: return root # If neither of the above conditions is satisfied, then the parent node is the LCA return root

In this example, we've created a simple Node class and a function lca() that finds the LCA using DFS.

Binary Lifted Bit Operators šŸ“

Using bit manipulation techniques, we can also find the LCA quickly. Here's an example implementation:

python
def set_bits(x, bit): return x | (1 << bit) def get_bit(x, bit): return (x >> bit) & 1 def lca_bit(n1, n2): if n1 == n2: return n1 # Find the maximum level level = 0 while n1 != 0 or n2 != 0: level += 1 n1 = get_bit(n1, level - 1) n2 = get_bit(n2, level - 1) # Find the LCA using the maximum level u = n1 v = n2 while u != v: u = nodes[u].parent v = nodes[v].parent return u

In this example, we've used bit manipulation to find the LCA quickly.

Quiz šŸ’”