Python से बाइनरी ट्री का लोएस्ट कॉमन एंसेस्टर (LCA) कैसे ढूंढें?

बाइनरी ट्री में दो नोड्स का LCA ढूंढने के लिए रिकर्सिव DFS: अगर दोनों सबट्रीज़ में नोड्स मिलें तो वर्तमान नोड LCA है।

एल्गोरिदम

• रिकर्सिव dfs(node) फंक्शन।
• अगर नोड x या y है: लेफ्ट/राइट चेक करें, कोई मिला तो वर्तमान नोड LCA।
• लेफ्ट और राइट दोनों से रिकर्सिव कॉल।
• अगर दोनों नॉन-None रिटर्न करें: वर्तमान नोड LCA।
• अन्यथा जो भी नॉन-None है उसे रिटर्न करें।

उदाहरण कोड

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

def solve(root, x, y):
    def dfs(node):
        if not node:
            return
        if node in [x, y]:
            left = dfs(node.left)
            right = dfs(node.right)
            if left or right:
                return node
        left = dfs(node.left)
        right = dfs(node.right)
        if left and right:
            return node
        return left or right
    return dfs(root)

# टेस्ट: ट्री [5,3,7,2,4,1,7,6,8,10], x=2, y=4 -> LCA = 3

इनपुट/आउटपुट

इनपुट: ट्री [5,3,7,2,4,1,7,6,8,10], नोड्स 2 और 4
आउटपुट: 3