Problem link ও উৎস
- **Original source:** Classic BST search exercise
- **Platform:** LeetCode —
- **Topic:** trees
- **Difficulty:** Easy
- **Pattern:** BST property
- **Basic idea inherited from:** Binary search, structure হিসেবে — প্রতি step-এ অর্ধেক ফেলে দাও, কিন্তু array না, একটা গাছে
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা **binary search tree (BST)**-র root আর একটা সংখ্যা `val` দেওয়া আছে। তোমার কাজ: যে node-এর value ঠিক `val`, সেই node (এবং তার subtree) ফেরত দাও। না থাকলে `None` ফেরাও।
BST property মনে রাখো: প্রতিটা node-এর বাঁ-subtree-র সব value তার চেয়ে **ছোট**, ডান-subtree-র সব value তার চেয়ে **বড়**।
```text
4
/ \
2 7
/ \
1 3 val = 2 → 2-node (subtree [2,1,3]) ফেরত
```
### Input ও output {#8-example-input-and-output}
```text
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]
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা sorted ডিকশনারিতে শব্দ খোঁজার কথা ভাবো। মাঝখানে খুলে দেখো; খোঁজা শব্দটা আগে এলে শুধু আগের অর্ধেকে যাও, পরে এলে পরের অর্ধেকে — বাকি অর্ধেকটা একবারও দেখো না। BST-তে প্রতিটা node ওই "মাঝখানে খোলা পাতা", আর তুমি প্রতি তুলনায় বইয়ের অর্ধেকটা ফেলে দাও।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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 বাদ দেওয়া:
```text
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/](../../04-stack-and-queue/README.md)-র stack পর্যন্ত লাগে না)।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
BST-র ordering প্রতিটা node-এ একটা "কোন দিকে যাব" সিদ্ধান্ত দেয়, তাই আমরা একটা মাত্র path ধরে সোজা নিচে নামি — পুরো tree ঘোরার দরকার নেই। এটাই BST-র superpower: search/insert/delete সব O(h) (concept.md দেখো), একপাশ সম্পূর্ণ উপেক্ষা করে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: BST property ভুলে যাই, tree-টাকে সাধারণ binary tree ধরে **পুরো ঘুরি** (যেকোনো traversal), প্রতিটা node-এ দেখি value == val কিনা।
```text
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-অর্ডার ধরে রেখেছে।
### ছবিতে বোঝা {#7-visual-explanation}
target `val = 3` খোঁজা; প্রতিটা node-এ তুলনা করে এক দিকে নামি (✗ মানে পুরো ওই দিক বাদ):
```text
4 3 < 4 → বাঁয়ে যাও, ডান-subtree (7) ✗
/ \
2 7 ✗ 3 > 2 → ডানে যাও, বাঁ-child (1) ✗
/ \
1✗ 3 3 == 3 → পেয়ে গেছি! এই node ফেরত
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `root = [4,2,7,1,3]`, `val = 3`:
1. node 4: 3 < 4 → বাঁয়ে নামো (ডান-subtree 7 পুরো বাদ)।
2. node 2: 3 > 2 → ডানে নামো (বাঁ-child 1 বাদ)।
3. node 3: 3 == 3 → **এই node ফেরত** (subtree [3])।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```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 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 নেই।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#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 বসাও) —