016 — Lowest Common Ancestor of a Binary Search Tree¶

Source¶

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 খোঁজা

1. Problem in simple words¶

তোমাকে একটা 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

2. Which basic idea does this inherit from?¶

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

3. What is the hidden math or logic?¶

লুকানো 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।

4. Which data structure is needed?¶

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

5. Why this data structure fits¶

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

6. Real-life analogy¶

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

7. Visual explanation¶

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

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

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

8. Example input and 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,...], p = 3, q = 5
Output: 4     (3 আর 5 দুজনেই 4-এর নিচে, আলাদা দিকে)

9. Brute force thinking¶

প্রথম সরল চিন্তা (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

10. Why brute force is slow¶

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

11. Key observation¶

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

12. Optimized intuition¶

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

13. Thinking tweak¶

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

14. Step-by-step dry run¶

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।

15. Python solution¶

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!")

16. Line-by-line code explanation¶

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)।

17. Output walkthrough¶

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!।

18. Time complexity¶

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

19. Space complexity¶

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

20. Common mistakes¶

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

21. Which basic problem this inherits from¶

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

22. Similar harder problems¶

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/

23. Pattern learned¶

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

24. Final summary¶

ভবিষ্যতের আমাকে: "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।