পাইথনে বাইনারি ট্রি থেকে একক চাইল্ড वाले নোড মুছে ফেলা

সমস্যা বিবরণ

একটি বাইনারি ট্রি দেওয়া আছে। যেসব নোডের শুধু একটি চাইল্ড আছে (বাম বা ডান, দুটো নয়), সেগুলো মুছে ফেলতে হবে। মুছে ফেলার মানে: নোডটি বাদ দিয়ে তার চাইল্ডকে প্যারেন্টের সাথে কানেক্ট কর देना।

উদাহরণ

ইনপুট ট্রি:

      1
     / \
    2   3
   /     \
  4       5
   \     / \
    6   7   8

আউটপুট ট্রি (ইনঅর্ডার): 6, 1, 7, 5, 8

ব্যাখ্যা: নোড ২ (শুধু ডান চাইল্ড ৬), নোড ৪ (শুধু ডান চাইল্ড ৬), নোড ৩ (শুধু বাম চাইল্ড ৭? না, ৩-এর দুটো চাইল্ড আছে ৭,৮ — তাই থাকে)। আপডেটেড ট্রি:

      1
     / \
    6   3
       / \
      7   8

অ্যালগরিদম: রিকার্সিভ পোস্ট-অর্ডার

1. বেস কেস: root is None → None রিটার্ন
2. লিফ নোড (দুই চাইল্ড নেই) → নিজে রিটার্ন
3. শুধু বাম চাইল্ড নেই → ডান সাবট্রি রিটার্ন (কারেন্ট নোড বাইপাস)
4. শুধু ডান চাইল্ড নেই → বাম সাবট্রি রিটার্ন
5. দুই চাইল্ড আছে → রিকার্সিভলি লেফট/রাইট প্রসেস করুন, আপডেট করুন, রিটার্ন

পাইথন কোড

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

def print_tree(root):
    if root:
        print_tree(root.left)
        print(root.data, end=', ')
        print_tree(root.right)

class Solution:
    def solve(self, root):
        if not root:
            return root
        
        # লিফ নোড
        if not root.left and not root.right:
            return root
        
        # শুধু একটি চাইল্ড: বাইপাস করুন
        if not root.left:
            return self.solve(root.right)
        if not root.right:
            return self.solve(root.left)
        
        # দুটি চাইল্ড: রিকার্সিভলি প্রসেস
        root.left = self.solve(root.left)
        root.right = self.solve(root.right)
        return root

# টেস্ট
ob = Solution()
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.right.right = TreeNode(5)
root.left.left.right = TreeNode(6)
root.right.right.left = TreeNode(7)
root.right.right.right = TreeNode(8)

res = ob.solve(root)
print_tree(res)  # 6, 1, 7, 5, 8,

ড্রাই রান

solve(1):
  left=solve(2):
    left=solve(4):
      left=None, right=solve(6)→6 (leaf)
      → return 6  (Node 4 bypassed)
    right=None
    → return 6  (Node 2 bypassed)
  right=solve(3):
    left=solve(7)→7, right=solve(8)→8
    → return 3 (both children exist)
  → return 1
Final: 1(left=6, right=3(7,8))
Inorder: 6, 1, 7, 3, 8 → wait, 3's left=7, right=8 → inorder: 6, 1, 7, 3, 8
But output says: 6, 1, 7, 5, 8... 
Ah, original tree has 5 as right child of 3, with 7,8 as children of 5.
Let me re-check: root.right.right = TreeNode(5), then 5.left=7, 5.right=8.
So 3 has only right child (5) → 3 gets bypassed!
solve(3): left=None, right=solve(5) → returns solve(5)
solve(5): left=7, right=8 → returns 5
So 3 is bypassed, 5 connects to 1.
Final: 1(left=6, right=5(7,8))
Inorder: 6, 1, 7, 5, 8 ✓

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(n) — প্রতিটি নোড একবার ভিজিট
• স্থান জটিলতা: O(h) — রিকার্শন স্ট্যাক, h = ট্রি হাইট

উপসংহার

• পোস্ট-অর্ডার ট্রাভার্সাল: চাইল্ড প্রসেস করে প্যারেন্টে রিটার্ন
• সিঙ্গেল চাইল্ড নোড "বাইপাস" হয় (প্যারেন্টের পয়েন্টার চাইল্ডকে পয়েন্ট করে)
• ট্রি স্ট্রাকচার প্রিজার্ভ থাকে, শুধু ডিগ্রি-১ নোড গুলো সরায়