009 — Search in a Binary Search Tree¶
Source¶
- Original source: Classic BST search exercise
- Platform: LeetCode — https://leetcode.com/problems/search-in-a-binary-search-tree/
- Topic: trees
- Difficulty: Easy
- Pattern: BST property
- Basic idea inherited from: Binary search, structure হিসেবে — প্রতি step-এ অর্ধেক ফেলে দাও, কিন্তু array না, একটা গাছে
1. Problem in simple words¶
তোমাকে একটা binary search tree (BST)-র root আর একটা সংখ্যা val দেওয়া আছে। তোমার কাজ: যে node-এর value ঠিক val, সেই node (এবং তার subtree) ফেরত দাও। না থাকলে None ফেরাও।
BST property মনে রাখো: প্রতিটা node-এর বাঁ-subtree-র সব value তার চেয়ে ছোট, ডান-subtree-র সব value তার চেয়ে বড়।
2. Which basic idea does this inherit from?¶
এটা সরাসরি binary search-এর tree-রূপ। array-তে binary search মাঝখানের element-এর সাথে তুলনা করে অর্ধেক ফেলে দেয়। BST-তে প্রতিটা node সেই "মাঝখান"-এর কাজ করে: target ছোট হলে বাঁয়ে যাও (ডান অর্ধেক বাদ), বড় হলে ডানে যাও (বাঁ অর্ধেক বাদ)। structure-টাই sorted অর্ডারকে ধারণ করে রাখে।
3. What is the hidden math or logic?¶
লুকানো logic হলো BST property কাজে লাগিয়ে প্রতি step-এ পুরো একটা subtree বাদ দেওয়া:
search(empty, val) = None
search(node, val) = node যদি val == node.val
= search(node.left, val) যদি val < node.val (ডান-অর্ধেক ফেলো)
= search(node.right, val) যদি val > node.val (বাঁ-অর্ধেক ফেলো)
মানে প্রতি তুলনায় তিন দিকের একটা বেছে এক ধাপে নামা। কখনো backtrack করতে হয় না — ordering নিশ্চিত করে target কোন দিকে আছে।
4. Which data structure is needed?¶
BST নিজেই data structure; search-এর জন্য বাড়তি কিছু লাগে না। recursion-এ শুধু call stack, আর iterative version-এ তো কেবল একটা pointer — O(1) extra (../../04-stack-and-queue/-র stack পর্যন্ত লাগে না)।
5. Why this data structure fits¶
BST-র ordering প্রতিটা node-এ একটা "কোন দিকে যাব" সিদ্ধান্ত দেয়, তাই আমরা একটা মাত্র path ধরে সোজা নিচে নামি — পুরো tree ঘোরার দরকার নেই। এটাই BST-র superpower: search/insert/delete সব O(h) (concept.md দেখো), একপাশ সম্পূর্ণ উপেক্ষা করে।
6. Real-life analogy¶
একটা sorted ডিকশনারিতে শব্দ খোঁজার কথা ভাবো। মাঝখানে খুলে দেখো; খোঁজা শব্দটা আগে এলে শুধু আগের অর্ধেকে যাও, পরে এলে পরের অর্ধেকে — বাকি অর্ধেকটা একবারও দেখো না। BST-তে প্রতিটা node ওই "মাঝখানে খোলা পাতা", আর তুমি প্রতি তুলনায় বইয়ের অর্ধেকটা ফেলে দাও।
7. Visual explanation¶
target val = 3 খোঁজা; প্রতিটা node-এ তুলনা করে এক দিকে নামি (✗ মানে পুরো ওই দিক বাদ):
4 3 < 4 → বাঁয়ে যাও, ডান-subtree (7) ✗
/ \
2 7 ✗ 3 > 2 → ডানে যাও, বাঁ-child (1) ✗
/ \
1✗ 3 3 == 3 → পেয়ে গেছি! এই node ফেরত
8. Example input and output¶
Input : root = [4,2,7,1,3], val = 2 -> Output: subtree rooted at 2 → [2,1,3]
Input : root = [4,2,7,1,3], val = 5 -> Output: None (নেই)
Input : root = [], val = 1 -> Output: None (খালি tree)
Input : root = [4,2,7], val = 4 -> Output: subtree rooted at 4 → [4,2,7]
9. Brute force thinking¶
প্রথম সরল চিন্তা: BST property ভুলে যাই, tree-টাকে সাধারণ binary tree ধরে পুরো ঘুরি (যেকোনো traversal), প্রতিটা node-এ দেখি value == val কিনা।
1) যেকোনো order-এ সব node visit করো
2) প্রতিটাতে দেখো node.val == val কিনা
3) মিললে সেই node ফেরত, না পেলে None
10. Why brute force is slow¶
সব node ঘোরা মানে O(n) — অথচ এটা BST, sorted। ordering থাকতেও সেটা কাজে না লাগিয়ে পুরো tree দেখা মানে binary search-এর সুবিধা ফেলে দেওয়া। প্রতি তুলনায় অর্ধেক বাদ দিলে কাজটা O(h)-এ নামে — balanced tree-তে O(log n), যা অনেক দ্রুত।
11. Key observation¶
মূল observation: প্রতিটা node-এ একটা মাত্র তুলনাই বলে দেয় target কোন দিকে আছে — তাই অন্য দিকটা পুরোপুরি উপেক্ষা করা যায়। দুই দিকে ভাগ হওয়ার (branch) দরকার নেই; সবসময় ঠিক একটা দিকে নামি, আর কখনো ফিরে আসি না।
12. Optimized intuition¶
root থেকে শুরু করো। প্রতিটা node-এ: val সমান হলে এই node ফেরাও; ছোট হলে node.left-এ নামো; বড় হলে node.right-এ নামো। None-এ পৌঁছালে target নেই, None ফেরাও। recursion বা একটা while-loop — দুটোই এক path বেয়ে সোজা নামে।
13. Thinking tweak¶
মোচড়: tree-টাকে "ঘোরার জিনিস" না ভেবে "প্রতি step-এ একটা হ্যাঁ/না প্রশ্ন" ভাবো — "target কি এর চেয়ে ছোট?" এক তুলনা = অর্ধেক tree বাদ। array-র binary search-এর সেই অর্ধেক-কাটা অভ্যাসটাই এখানে গাছে প্রয়োগ করো; structure তোমার হয়ে sorted-অর্ডার ধরে রেখেছে।
14. Step-by-step dry run¶
Input root = [4,2,7,1,3], val = 3:
- node 4: 3 < 4 → বাঁয়ে নামো (ডান-subtree 7 পুরো বাদ)।
- node 2: 3 > 2 → ডানে নামো (বাঁ-child 1 বাদ)।
- node 3: 3 == 3 → এই node ফেরত (subtree [3])।
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 search_bst(node, val):
while node is not None: # path বেয়ে সোজা নামি
if val == node.val: # পেয়ে গেছি
return node
if val < node.val: # target ছোট → বাঁয়ে (ডান-অর্ধেক বাদ)
node = node.left
else: # target বড় → ডানে (বাঁ-অর্ধেক বাদ)
node = node.right
return None # None-এ পৌঁছালাম → target নেই
# ---- tests ----
root = build_tree([4, 2, 7, 1, 3])
found = search_bst(root, 2)
assert found is not None and found.val == 2 # node 2 পাওয়া গেল
assert found.left.val == 1 and found.right.val == 3 # তার subtree সঠিক
assert search_bst(root, 5) is None # নেই
assert search_bst(build_tree([]), 1) is None # খালি tree
assert search_bst(build_tree([4, 2, 7]), 4).val == 4 # root নিজেই match
print("সব test pass!")
16. Line-by-line code explanation¶
while node is not None— যতক্ষণ আসল node-এ আছি, path বেয়ে নামতে থাকি।if val == node.val: return node— match পেলে এই node (ও তার subtree) ফেরত।if val < node.val: node = node.left— মূল চাল: target ছোট, তাই বাঁয়ে; পুরো ডান-subtree বাদ।else: node = node.right— target বড়, তাই ডানে; পুরো বাঁ-subtree বাদ।return None— loop শেষ মানেNone-এ পৌঁছেছি, target নেই।
17. Output walkthrough¶
[4,2,7,1,3]-এ val=2: 2 < 4 → বাঁয়ে → node 2 পাওয়া গেল, তার left 1 ও right 3 সঠিক। val=5: 5 > 4 → ডানে → 5 > 7? না, 5 < 7 → বাঁয়ে → None → নেই। খালি tree → None; [4,2,7]-এ val=4 → root-ই match। সব assert pass, শেষে print: সব test pass!।
18. Time complexity¶
O(h) — h = tree-র height; প্রতি step-এ এক স্তর নামি, কখনো branch করি না। balanced BST-তে O(log n), একপাশে ঝোলা chain-এ O(n)। (concept.md-র table দেখো।)
19. Space complexity¶
O(1) — iterative version-এ শুধু একটা pointer; কোনো বাড়তি data structure নেই। (recursive লিখলে call stack-এর জন্য O(h) হতো।)
20. Common mistakes¶
- BST property না খাটিয়ে পুরো tree ঘোরা → অকারণে O(n)।
<আর>উল্টে দেওয়া → ভুল দিকে নেমে target মিস।None-এ পৌঁছে None ফেরাতে ভুলে গিয়েNone.valছোঁয়া → AttributeError।
21. Which basic problem this inherits from¶
ভিত্তি: array-র binary search (অর্ধেক-কাটা) আর traversal-patterns.md-র Pattern C (BST property)। concept.md-র BST সংজ্ঞা মাথায় রাখলে "এক তুলনা = অর্ধেক বাদ" স্বাভাবিক লাগে।
22. Similar harder problems¶
- Insert into a Binary Search Tree (একই path খুঁজে None জায়গায় নতুন node বসাও) — https://leetcode.com/problems/insert-into-a-binary-search-tree/
- Lowest Common Ancestor of a BST (BST search, একসাথে দুটো target) — https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/ (এই tracker-এর #16)
- Validate Binary Search Tree (পুরো tree সত্যিই BST কিনা bounds দিয়ে যাচাই) — https://leetcode.com/problems/validate-binary-search-tree/ (#14)
23. Pattern learned¶
BST one-way descent: প্রতিটা node-এ এক তুলনা করে ঠিক একটা দিকে নামো, অন্য subtree পুরো বাদ; O(h)-এ target পাও। insert, floor/ceiling, range query — সবই এই অর্ধেক-কাটা চালের উপর দাঁড়ায়।
24. Final summary¶
ভবিষ্যতের আমাকে: "BST search = root থেকে নামো; ছোট হলে বাঁয়ে, বড় হলে ডানে, সমান হলে পেয়েছ।" "BST", "sorted tree", "closest value" শুনলেই এই অর্ধেক-কাটা descent মনে পড়বে। মূল চাবি: ordering থাকলে কখনো পুরো tree ঘোরবে না।
মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।