পাইথনে BST-এর মেডিয়ান O(n) সময় এবং O(1) স্পেসে বের করা

ধরা যাক একটি বাইনারি সার্চ ট্রি (BST) আছে। আমাদের এর মেডিয়ান বের করতে হবে। জোড় নোড হলে মেডিয়ান = (n/2th নোড + (n+1)/2th নোড) / 2। বিজোড় নোড হলে মেডিয়ান = (n+1)/2th নোড।

ইনপুট ট্রি দেওয়া আছে (চিত্রে), আউটপুট হবে 7।

সমাধানের ধাপসমূহ (মরিস ট্রাভারসাল)

• যদি root is None: return 0
• node_count := ট্রির মোট নোড সংখ্যা (মরিস ট্রাভারসাল দিয়ে)
• count_curr := 0, current := root
• while current != None:
  • যদি current.left is None:
    • count_curr বাড়ান
    • মেডিয়ান চেক করুন (অড/ইভেন অনুযায়ী)
    • previous := current, current := current.right
  • অন্যথায়:
    • previous := current.left
    • while previous.right != None and previous.right != current: previous := previous.right
    • যদি previous.right is None: previous.right := current; current := current.left
    • অন্যথায়: previous.right := None; count_curr বাড়ান; মেডিয়ান চেক করুন; previous := current; current := current.right

উদাহরণ

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
def number_of_nodes(root):
    node_count = 0
    if root == None: return node_count
    current = root
    while current != None:
        if current.left == None:
            node_count += 1
            current = current.right
        else:
            previous = current.left
            while previous.right != None and previous.right != current:
                previous = previous.right
            if previous.right == None:
                previous.right = current
                current = current.left
            else:
                previous.right = None
                node_count += 1
                current = current.right
    return node_count
def calculate_median(root):
    if root == None: return 0
    node_count = number_of_nodes(root)
    count_curr = 0
    current = root
    while current != None:
        if current.left == None:
            count_curr += 1
            if node_count % 2 != 0 and count_curr == (node_count + 1)//2:
                return previous.data
            elif node_count % 2 == 0 and count_curr == (node_count//2)+1:
                return (previous.data + current.data)//2
            previous = current
            current = current.right
        else:
            previous = current.left
            while previous.right != None and previous.right != current:
                previous = previous.right
            if previous.right == None:
                previous.right = current
                current = current.left
            else:
                previous.right = None
                previous = previous
                count_curr += 1
                if node_count % 2 != 0 and count_curr == (node_count + 1)//2:
                    return current.data
                elif node_count % 2 == 0 and count_curr == (node_count//2)+1:
                    return (previous.data + current.data)//2
                previous = current
                current = current.right
# ট্রি তৈরি
root = TreeNode(7)
root.left = TreeNode(4)
root.right = TreeNode(9)
root.left.left = TreeNode(2)
root.left.right = TreeNode(5)
root.right.left = TreeNode(8)
root.right.right = TreeNode(10)
print(calculate_median(root))

ইনপুট

root = TreeNode(7)
root.left = TreeNode(4)
root.right = TreeNode(9)
root.left.left = TreeNode(2)
root.left.right = TreeNode(5)
root.right.left = TreeNode(8)
root.right.right = TreeNode(10)

আউটপুট

7