Python দিয়ে পেরেন্ট পয়েন্টার ব্যবহার করে বাইনারি ট্রির লোয়েস্ট কমন অ্যান্সেস্টর বের করার প্রোগ্রাম

মান লাগিয়ে, আমাদের একটি বাইনারি ট্রি এবং দুটি নির্দিষ্ট নোড x এবং y দেওয়া আছে। আমাদের বাইনারি ট্রি থেকে এই দুটি নোডের লোয়েস্ট কমন অ্যান্সেস্টর বের করতে হবে। বাইনারি ট্রিতে লোয়েস্ট কমন অ্যান্সেস্টর হল সেই নোড যা সবচেয়ে নিচে অবস্থিত এবং যার ডিসেন্ডেন্ট হিসেবে x এবং y উভয় নোড থাকে। একটি নির্দিষ্ট নোড নিজেরাও তার ডিসেন্ডেন্ট হতে পারে। আমাদের নোডটি বের করে রিটার্ন করতে হবে।

ট্রির নোড কাঠামো নিচের মতো:

TreeNode:
    data: 
    left: 
    right: 
    parent: 

সমাধান খুঁজতে পেরেন্ট পয়েন্টার ব্যবহার করতে হবে।

যেমন, ইনপুট যদি এমন হয়:

এবং x = 3, y = 7; তবে আউটপুট হবে 5।

৩ এবং ৭ উভয়ই ৫-এর ডিসেন্ডেন্ট, তাই উত্তর হবে ৫।

এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব:

• path_p_r := একটি নতুন লিস্ট
• x null না হওয়া পর্যন্ত:
  • x path_p_r-এ যোগ করুন
  • x := x.parent
• y null না হওয়া পর্যন্ত:
  • যদি y path_p_r-এ থাকে, তবে y রিটার্ন করুন
  • 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 insert(temp,data):
    que = []
    que.append(temp)
    while (len(que)):
        temp = que[0]
        que.pop(0)
        if (not temp.left):
            if data is not None:
                temp.left = TreeNode(data, parent=temp)
            else:
                temp.left = TreeNode(0,parent=temp)
            break
        else:
            que.append(temp.left)
        if (not temp.right):
            if data is not None:
                temp.right = TreeNode(data,parent=temp)
            else:
                temp.right = TreeNode(0,parent=temp)
            break
        else:
            que.append(temp.right)
def make_tree(elements):
    Tree = TreeNode(elements[0])
    for element in elements[1:]:
        insert(Tree, element)
    return Tree
def search_node(root, element):
    if (root == None):
        return None
    if (root.data == element):
        return root
    res1 = search_node(root.left, element)
    if res1:
        return res1
    res2 = search_node(root.right, element)
    return res2
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
root = make_tree([5, 3, 7, 2, 4, 1, 7, 6, 8, 10])
print(solve(search_node(root, 3), search_node(root, 7)).data)

ইনপুট

[5, 3, 7, 2, 4, 1, 7, 6, 8, 10], 3, 7

আউটপুট

5