পাইথনে বাইনারি ট্রিতে দুটি নোডের মধ্যকার দূরত্ব খুঁজে বের করার প্রোগ্রাম

আমাদের একটি বাইনারি ট্রি দেওয়া আছে এবং আমাদের এতে দুটি নোডের মধ্যকার দূরত্ব বের করতে বলা হয়েছে। আমরা গ্রাফের মত দুই নোডের মধ্যকার এজগুলো বের করব এবং এজ সংখ্যাটা বা দূরত্বটি রিটার্ন করব। একটি ট্রি নোডের কাঠামো নিচের মতো:

data: 
right: 
left:

উদাহরণস্বরূপ, ইনপুট একটি বাইনারি ট্রি এবং নোড ২ এবং ৮ হলে আউটপুট হবে ৪।

নোড ২ এবং ৮ এর মধ্যকার এজগুলো হলো: (2, 3), (3, 5), (5, 7), এবং (7, 8)। পথে ৪টি এজ আছে, তাই দূরত্ব ৪।

সমাধানের ধাপসমূহ

findLca() ফাংশন ডিফাইন করুন। এটি root, p, q ইনপুট নেবে:
- যদি root == None হয়, তবে None রিটার্ন করুন
- যদি root.data (p,q)-এর যেকোনো একটি হয়, তবে root রিটার্ন করুন
- left := findLca(root.left, p, q)
- right := findLca(root.right, p, q)
- যদি left এবং right দুটোই None না হয়, তবে root রিটার্ন করুন
- left বা right রিটার্ন করুন
findDist() ফাংশন ডিফাইন করুন। এটি root, data ইনপুট নেবে:
- queue := একটি নতুন deque
- (root, 0) জোড়াটি queue-এর শেষে যোগ করুন
- queue খালি না হওয়া পর্যন্ত লুপ চালান:
  - current := queue-এর বামপাশের জোড়ার প্রথম মান
  - dist := queue-এর বামপাশের জোড়ার দ্বিতীয় মান
  - যদি current.data == data হয়, তবে dist রিটার্ন করুন
  - যদি current.left != None হয়, তবে (current.left, dist+1) কিউতে যোগ করুন
  - যদি current.right != None হয়, তবে (current.right, dist+1) কিউতে যোগ করুন
node := findLca(root, p, q)
findDist(node, p) + findDist(node, q) রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালোভাবে বুঝার জন্য:

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

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)
            else:
                temp.left = TreeNode(0)
            break
        else:
            que.append(temp.left)
        if not temp.right:
            if data is not None:
                temp.right = TreeNode(data)
            else:
                temp.right = TreeNode(0)
            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 findLca(root, p, q):
    if root is None:
        return None
    if root.data in (p, q):
        return root
    left = findLca(root.left, p, q)
    right = findLca(root.right, p, q)
    if left and right:
        return root
    return left or right

def findDist(root, data):
    queue = collections.deque()
    queue.append((root, 0))
    while queue:
        current, dist = queue.popleft()
        if current.data == data:
            return dist
        if current.left:
            queue.append((current.left, dist+1))
        if current.right:
            queue.append((current.right, dist+1))

def solve(root, p, q):
    node = findLca(root, p, q)
    return findDist(node, p) + findDist(node, q)

root = make_tree([5, 3, 7, 2, 4, 6, 8])
print(solve(root, 2, 8))

ইনপুট

root = make_tree([5, 3, 7, 2, 4, 6, 8]) print(solve(root, 2, 8))