## Similar Problems

Similar Problems not available

# Smallest Common Region - Leetcode Solution

## Companies:

LeetCode: Smallest Common Region Leetcode Solution

Difficulty: Medium

Topics: hash-table depth-first-search string breadth-first-search tree array

The Smallest Common Region problem on LeetCode is a algorithmic problem that requires finding the lowest common ancestor of two given nodes in a tree structure. The solution can be implemented by following steps:

Step 1: Create a hash-map to store the parent nodes of each node in the tree. - Traverse the tree in any order (pre-order, in-order, post-order). - For each node, add its parent to the hash-map with node as key and parent as value.

Step 2: Create a set to store the ancestors of first node. - Traverse from the first node up to root node and add all the ancestors to the set.

Step 3: Traverse from second node up to root node and check if it has ancestor in the set. - If yes, return that node as the Lowest Common Ancestor.

Step 4: Repeat step 3 until root node is reached. - If none of the nodes have a common ancestor, return root node as the Lowest Common Ancestor.

Python implementation:

# Definition for a binary tree node.

# class TreeNode:

# def **init**(self, x):

# self.val = x

# self.left = None

# self.right = None

class Solution: def findSmallestRegion(self, regions: List[str], region1: str, region2: str) -> str: parents = {}

```
# traverse tree and store parent in hash-map
for region in regions:
parent = region[0]
for child in region[1:]:
parents[child] = parent
# create set of ancestors for first node
ancestors = set()
while region1 in parents:
ancestors.add(region1)
region1 = parents[region1]
ancestors.add(region1)
# check for ancestor of second node in the ancestors set
while region2 not in ancestors:
region2 = parents[region2]
return region2
```

The time complexity of the algorithm is O(n) where n is the number of nodes in the tree. The space complexity is also O(n) for storing the parent mapping.

## Smallest Common Region Solution Code

`1`