পাইথনে বাইনারি সার্চ ট্রিতে লোয়েস্ট কমন আনসেসটর

একটি বাইনারি সার্চ ট্রি (BST) দেওয়া থাকে। দুটি নোড p এবং q-র লোয়েস্ট কমন আনসেসটর (LCA) বের করতে হবে। LCA হল সাবচে নিচের নোড যা p এবং q উভয়েরই আনসেসটর। উদাহরণে ট্রি [6,2,8,0,4,7,9,null,null,3,5] এর জন্য ২ এবং ৮-এর LCA হল ৬।

সমাধানের পদ্ধতি

1. যদি রুট খালি হয়, None রিটার্ন করুন।
2. যদি p বা q রুটের সমান হয়, রুট রিটার্ন করুন।
3. বাম এবং ডান সাবট্রিতে রিকারসিভলি LCA খুঁজুন।
4. যদি উভয় সাইড থেকে নন-নাল রিটার্ন হয়, তবে রুটই LCA।
5. অন্যথায় যে সাইড থেকে নন-নাল আসে, সেটি রিটার্ন করুন।

উদাহরণ কোড

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

class Solution():
    def lowestCommonAncestor(self, root, p, q):
        if not root:
            return None
        if p == root or q == root:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            return root
        return left or right

# ট্রি বানানোর হেল্পার ফাংশনগুলো (insert, make_tree, search_node) উপরের উদাহরণের মতো
root = make_tree([6,2,8,0,4,7,9,None,None,3,5])
ob1 = Solution()
op = ob1.lowestCommonAncestor(root, search_node(root, 2), search_node(root, 8))
print(op.data)

ইনপুট

[6,2,8,0,4,7,9,null,null,3,5] 2 8

আউটপুট

6