016 — Lowest Common Ancestor of a Binary Search Tree¶

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

Original source: Classic BST ancestor-search exercise
Platform: LeetCode — https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
Topic: trees
Difficulty: Medium
Pattern: BST property + LCA
Basic idea inherited from: BST search, একসাথে দুটো target — split-point খোঁজা

প্রশ্ন ও উদাহরণ¶

সহজ করে প্রশ্ন¶

তোমাকে একটা Binary Search Tree আর দুটো node p ও q দেওয়া আছে। তোমার কাজ: তাদের lowest common ancestor (LCA) বের করা — মানে সবচেয়ে গভীর সেই node যার subtree-তে p আর q দুজনেই আছে (একটা node নিজেও নিজের ancestor ধরা হয়)।

উদাহরণ

        6
       / \
      2   8        LCA(2, 8) = 6   (একদিকে 2, অন্যদিকে 8)
     / \ / \
    0  4 7  9      LCA(2, 4) = 2   (2 নিজেই 4-এর ancestor)
      / \
     3   5

Input ও output¶

উদাহরণ

Input : root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6

Input : root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2     (2 নিজেই 4-এর ancestor)

Input : root = [6,2,8,0,4,7,9,null,null,3,5], p = 3, q = 5
Output: 4     (3 আর 5 দুজনেই 4-এর নিচে, আলাদা দিকে)

চেনা উদাহরণে বোঝা¶

একটা পারিবারিক বংশলতিকা ভাবো যেখানে বাঁ দিকে ছোটরা, ডান দিকে বড়রা সাজানো (id দিয়ে)। দুজন আত্মীয়ের সবচেয়ে কাছের common পূর্বপুরুষ খুঁজতে শীর্ষ থেকে নামো: দুজনেই কোনো শাখার বাঁয়ে পড়লে সেই শাখায় নামো, দুজনেই ডানে পড়লে ডানে — যেখানে একজন এক দিকে আর আরেকজন অন্য দিকে, সেই ব্যক্তিই তাদের meeting point।

ভিত্তির ধারণা¶

আগের কোন ধারণাটি লাগবে¶

এটা সরাসরি BST search থেকে আসে, কিন্তু একসাথে দুটো target নিয়ে। সাধারণ BST search-এ value-র সাথে তুলনা করে এক দিকে নামি। এখানে দুটো value নিয়ে নামি: দুটোই ছোট হলে বাঁয়ে, দুটোই বড় হলে ডানে। যেখানে তারা প্রথমবার আলাদা দিকে যায় (বা একটা current node-এর সমান হয়), সেটাই fork — মানে LCA।

ভেতরের যুক্তি¶

লুকানো logic হলো ordering ব্যবহার করে fork খোঁজা:

উদাহরণ

current node-এ দাঁড়িয়ে:
    p.val আর q.val দুটোই < node.val  → LCA বাঁয়ে
    p.val আর q.val দুটোই > node.val  → LCA ডানে
    নাহলে (একটা ≤ node ≤ আরেকটা)     → node-ই LCA (split point)

split point হলো প্রথম node যেখানে দুজনের path আলাদা হয় — BST-তে এটাই lowest common ancestor।

কী দিয়ে তথ্য রাখব¶

কোনো extra data structure লাগে না। শুধু একটা pointer যা root থেকে শুরু করে নামে (iterative, O(1) extra space), অথবা recursion call stack (একই logic, recursive রূপে)।

এটি কেন উপযুক্ত¶

BST-র ordering প্রতিটা comparison-এ একটা পুরো subtree বাদ দিতে দেয়, তাই আমাদের শুধু একটা path-এ নামলেই হয় — কোনো queue বা stack লাগে না। একটা pointer-ই যথেষ্ট, কারণ আমরা কখনো ফিরে আসি না বা branch করি না; প্রতিটা ধাপে exactly এক দিকে নামি।

ধাপে ধাপে সমাধান¶

প্রথম সরল উপায়¶

প্রথম সরল চিন্তা (BST property ব্যবহার না করে): root থেকে p পর্যন্ত পুরো path বের করি, আর q পর্যন্ত পুরো path বের করি, তারপর দুই path-এ শেষ যে common node, সেটাই LCA।

উদাহরণ

1) path to 2: [6, 2]
2) path to 8: [6, 8]
3) দুই path-এর শেষ common node = 6

কোথায় বেশি কাজ হচ্ছে¶

এটা ঠিক উত্তর দেয়, কিন্তু দুটো আলাদা path বের করতে দুবার tree খোঁজা, আর সেই path-গুলো জমিয়ে রাখা — extra memory আর কাজ। BST-তে এর দরকারই নেই: ordering আমাদের একটা মাত্র downward walk-এ fork ধরিয়ে দেয়, কোনো path জমানো ছাড়াই।

যে বিষয়টি খেয়াল করতে হবে¶

মূল observation: BST-তে p আর q একসাথে current node-এর কোন দিকে পড়ে, সেটাই বলে দেয় কোথায় নামতে হবে। যেই মুহূর্তে তারা আলাদা দিকে পড়ে (বা একটা current node হয়), সেই node-ই lowest common ancestor — আর নামার দরকার নেই।

আরও কম কাজে সমাধান¶

এটা একটা guided downward walk (BST search-এর জোড়া রূপ): root থেকে শুরু করো; দুটোই ছোট হলে বাঁয়ে, দুটোই বড় হলে ডানে; প্রথম যেখানে split (একটা ≤ node ≤ আরেকটা) সেখানেই উত্তর। মাত্র O(h) ধাপ — height-এর সমান, কারণ প্রতি ধাপে এক level নামি।

ভাবনার পরিবর্তন¶

মোচড়: "দুটো path আলাদা করে বের করব" ভাবা বন্ধ করো। বরং ভাবো "দুজনকে একসাথে নিয়ে নামব, আর যেখানে তারা প্রথম আলাদা হয় সেখানেই থামব।" ordering-টাই তোমার কম্পাস — কোন দিকে নামতে হবে তা প্রতি node-এ একটাই comparison-এ বলে দেয়।

ছবিতে বোঝা¶

LCA(2, 8) খুঁজতে শীর্ষ থেকে নামার পথ:

উদাহরণ

        6   ← 2 < 6 আর 8 > 6 → split! এখানেই থামো
       / \
      2   8
     / \ / \
    0  4 7  9

2 বাঁয়ে, 8 ডানে → 6-ই fork → LCA = 6

ছোট input-এ ধাপে ধাপে¶

Input tree root 6, p = 2, q = 8:

node = 6। 2 < 6 কিন্তু 8 > 6 → একটা বাঁয়ে, একটা ডানে → split! node 6-ই LCA → return 6।

আরেকটা: p = 3, q = 5 (দুজনেই 4-এর নিচে):

node = 6। 3 < 6 আর 5 < 6 → দুটোই বাঁয়ে → node = 2।
node = 2। 3 > 2 আর 5 > 2 → দুটোই ডানে → node = 4।
node = 4। 3 < 4 আর 5 > 4 → split → return 4।

কোড ও ব্যাখ্যা¶

Python¶

Python

from collections import deque


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


def build_tree(values):
    """level-order list (None = missing child) থেকে tree বানায়।"""
    if not values:
        return None
    root = TreeNode(values[0])
    q = deque([root])
    i = 1
    while q and i < len(values):
        node = q.popleft()
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            q.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            q.append(node.right)
        i += 1
    return root


def find(root, val):
    """BST property দিয়ে value খুঁজে node ফেরত দেয় (test helper)।"""
    node = root
    while node:
        if val < node.val:
            node = node.left
        elif val > node.val:
            node = node.right
        else:
            return node
    return None


def lca_bst(root, p, q):
    node = root
    while node:
        if p.val < node.val and q.val < node.val:   # দুটোই ছোট
            node = node.left                         # বাঁয়ে নামো
        elif p.val > node.val and q.val > node.val:  # দুটোই বড়
            node = node.right                        # ডানে নামো
        else:
            return node                              # split point = LCA
    return None


# ---- tests ----
root = build_tree([6, 2, 8, 0, 4, 7, 9, None, None, 3, 5])
assert lca_bst(root, find(root, 2), find(root, 8)).val == 6
assert lca_bst(root, find(root, 2), find(root, 4)).val == 2
assert lca_bst(root, find(root, 3), find(root, 5)).val == 4
assert lca_bst(root, find(root, 0), find(root, 5)).val == 2
print("সব test pass!")

কোডের প্রতিটি অংশ¶

node = root — root থেকে নামা শুরু।
if p.val < node.val and q.val < node.val: node = node.left — দুজনেই ছোট, মানে দুজনেই বাঁ subtree-তে → বাঁয়ে নামো।
elif p.val > node.val and q.val > node.val: node = node.right — দুজনেই বড় → ডানে নামো।
else: return node — একজন এক দিকে আর আরেকজন অন্য দিকে (বা একজন current node) → এটাই split point, lowest common ancestor।
find helper test-এর জন্য value থেকে node বের করে (BST search)।

Output মিলিয়ে দেখা¶

build_tree([6,2,8,0,4,7,9,None,None,3,5]) ওই BST বানায়; lca_bst LCA(2,8) = 6 ফেরত দেয় — assert pass। LCA(2,4) = 2 (একটা অন্যটার ancestor), LCA(3,5) = 4, LCA(0,5) = 2 — সব pass। শেষে print: সব test pass!।

খরচ ও সাধারণ ভুল¶

সময়¶

O(h) — root থেকে split point পর্যন্ত নামতে height h-এর সমান ধাপ। Balanced BST-তে O(log n), skewed-এ O(n)। দুবার tree খোঁজার brute force-এর চেয়ে কম।

অতিরিক্ত জায়গা¶

O(1) — iterative version শুধু একটা pointer রাখে, কোনো stack বা recursion ছাড়াই। (recursive লিখলে call stack-এর জন্য O(h) হতো।)

যে ভুলগুলো এড়াতে হবে¶

general binary tree-র postorder LCA এখানে লাগানো — ঠিক কাজ করবে কিন্তু BST-র সস্তা ordering-শর্টকাট মিস করবে (O(n) বনাম O(h))।
"একটা node নিজের ancestor হতে পারে" কেস ভুলে যাওয়া — তখন p current node হলে split-শর্ত else-এ পড়ে, যা ঠিক।
শুধু < / > ব্যবহার করতে গিয়ে সমান-কেস বাদ দেওয়া; else branch সেটা সামলায়।

শেখা ও পরের অনুশীলন¶

ভিত্তির সঙ্গে সম্পর্ক¶

ভিত্তি: traversal-patterns.md-র Pattern D (LCA) আর Pattern C (BST property), সাথে BST search। ordering থাকায় path জমানোর দরকার নেই — একটা guided walk-ই fork ধরিয়ে দেয়।

পরের অনুশীলন¶

LCA of a Binary Tree (ordering নেই, তাই postorder খোঁজা লাগে) — https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/ (এই tracker-এর #17)
Lowest Common Ancestor of a BST III (parent pointer সহ) — https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/ (variant)
Insert into a Binary Search Tree (একই guided-walk কৌশল) — https://leetcode.com/problems/insert-into-a-binary-search-tree/

কৌশলটি মনে রাখুন¶

Guided BST descent for two targets: ordering ব্যবহার করে দুটো target-কে একসাথে নিয়ে নামো; দুজনেই এক দিকে থাকলে সেদিকে নামো, আলাদা হলেই থামো। এটাই BST-তে LCA-র সস্তা চাল — কোনো path জমানো বা পুরো tree ঘোরা ছাড়াই O(h)।

নিজেকে যাচাই করুন¶

ভবিষ্যতের আমাকে: "BST-তে LCA = root থেকে নামো, দুজনেই এক দিকে হলে সেদিকে, split হলে থামো।" ordering থাকায় এটা O(h), general tree-র postorder LCA-র চেয়ে সহজ ও দ্রুত। 'BST + দুটো node-এর সম্পর্ক' দেখলেই এই guided-descent চালটা মনে করবে।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।