Python से पैरेंट पॉइंटर्स का उपयोग करके बाइनरी ट्री का LCA कैसे ढूंढें?

पैरेंट पॉइंटर्स होने पर, एक नोड के सभी एंसेस्टर्स को सेट में स्टोर करके दूसरे नोड के एंसेस्टर्स चेक करें।

एल्गोरिदम

• path_p_r लिस्ट में x के सभी एंसेस्टर्स (रूट तक) स्टोर करें।
• y से ऊपर जाते हुए चेक करें: अगर y path_p_r में है, तो वही LCA है।
• नहीं मिला तो y = y.parent जारी रखें।

उदाहरण कोड

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

def solve(x, y):
    path_p_r = []
    while x:
        path_p_r.append(x)
        x = x.parent
    while y:
        if y in path_p_r:
            return y
        y = y.parent

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

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

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