Trees — Traversal Patterns and Problem Patterns¶
Part 1 চারটা traversal-কে trivia না, tool বানায়: প্রতিটা visit order-এর মানে কী আর কখন সেটাই সঠিক পছন্দ। Part 2 cover করে তাদের উপর দাঁড়ানো বারবার-ফেরা tree problem-এর আকৃতিগুলো।
Part 1 — চারটা traversal, tool হিসেবে¶
Inorder: Left → Node → Right¶
Order-টার মানে: "ছোট-দিকের সবকিছু আগে, মাঝে আমি, বড়-দিক পরে।" BST-তে এটা value-গুলো sorted ascending order-এ বের করে — structure-টার superpower।
Recursive sketch:
def inorder(node, out):
if node is None:
return
inorder(node.left, out)
out.append(node.val) # the visit, sandwiched
inorder(node.right, out)
Iterative sketch (explicit stack call stack-এর জায়গা নেয় — দেখো ../04-stack-and-queue/):
def inorder_iter(root):
out, stack, node = [], [], root
while node or stack:
while node: # slide all the way left,
stack.append(node) # remembering the path
node = node.left
node = stack.pop() # deepest unvisited
out.append(node.val)
node = node.right # then give the right side its turn
return out
সঠিক tool যখন: একটা BST-র content sorted order-এ দরকার; BST-তে k-th smallest (k-টা visit-এর পর থেমে যাও); inorder sequence কঠোরভাবে increasing কি না দেখে BST check করা।
Problems: Binary Tree Inorder Traversal https://leetcode.com/problems/binary-tree-inorder-traversal/, Kth Smallest Element in a BST https://leetcode.com/problems/kth-smallest-element-in-a-bst/।
Preorder: Node → Left → Right¶
Order-টার মানে: "আগে আমি, তারপর আমার পুরো বাঁ-জগৎ, তারপর আমার পুরো ডান-জগৎ।" Parent তার সব descendant-এর আগে আসে — output থেকে tree-টা top-down আবার বানানো যায়, এজন্যই preorder হলো copy / serialize-এর order।
def preorder(node, out):
if node is None:
return
out.append(node.val) # visit on ARRIVAL
preorder(node.left, out)
preorder(node.right, out)
Iterative sketch: root-কে একটা stack-এ push করো; pop করো, visit করো, RIGHT তারপর LEFT push করো (যাতে left আগে pop হয়)।
def preorder_iter(root):
out, stack = [], [root] if root else []
while stack:
node = stack.pop()
out.append(node.val)
if node.right: stack.append(node.right)
if node.left: stack.append(node.left)
return out
সঠিক tool যখন: tree clone করা; string-এ serialize করে (None marker সহ) আবার বানানো; এমন যেকোনো কাজ যেখানে child process হওয়ার আগে parent-এর decision লাগবে (যেমন path-so-far নিচে পাঠানো)।
Problems: Serialize and Deserialize Binary Tree https://leetcode.com/problems/serialize-and-deserialize-binary-tree/, Construct Binary Tree from Preorder and Inorder Traversal https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/।
Postorder: Left → Right → Node¶
Order-টার মানে: "আমার দুই child সম্পূর্ণ শেষ, তারপর আমি।" এটাই children-before-parent কাজের order: child-দের উত্তর থেকে node-এর উত্তর হিসাব করা, বা নিরাপদে delete করা (folder খালি হলে তবেই সেটা সরানো যায়)।
def postorder(node, out):
if node is None:
return
postorder(node.left, out)
postorder(node.right, out)
out.append(node.val) # visit on DEPARTURE
সঠিক tool যখন: height, subtree size, subtree sum, "is balanced", node free/delete করা, expression tree evaluate করা (operator-এর আগে operand), আর tree DP-র সবকিছু। Problem statement-এ "combine the results of the subtrees" থাকলেই সেটা postorder।
Problems: Maximum Depth of Binary Tree https://leetcode.com/problems/maximum-depth-of-binary-tree/, Balanced Binary Tree https://leetcode.com/problems/balanced-binary-tree/, Diameter of Binary Tree https://leetcode.com/problems/diameter-of-binary-tree/।
Level order: layer by layer — queue দিয়ে BFS¶
Order-টার মানে: root থেকে দূরত্ব। সব depth-1 node, তারপর সব depth-2 node... Engine হলো ../04-stack-and-queue/-এর একটা FIFO queue; child পেছনে enqueue হয়, তাই পরেরটা শুরুর আগে একটা layer পুরো খালি হয়ে যায়।
from collections import deque
def level_order(root):
if not root:
return []
levels, q = [], deque([root])
while q:
size = len(q) # nodes currently in q = exactly one level
level = []
for _ in range(size):
node = q.popleft()
level.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
levels.append(level)
return levels
size = len(q) snapshot-টাই level-আলাদা-করার কায়দা — এটা ছাড়া BFS order-এই visit হবে কিন্তু layer-এর সীমানা হারিয়ে যাবে।
সঠিক tool যখন: per-level ভাষায় বলা যেকোনো কিছু (level average, zigzag, right side view), unweighted structure-এ shortest path (BFS সবচেয়ে কাছেরটা আগে পায়), minimum depth (প্রথম যে leaf-এর দেখা মেলে সেটাই উত্তর — DFS অমন আগে থামতে পারে না)।
Problems: Binary Tree Level Order Traversal https://leetcode.com/problems/binary-tree-level-order-traversal/, Binary Tree Right Side View https://leetcode.com/problems/binary-tree-right-side-view/।
এক নিঃশ্বাসে বাছাই¶
| You need... | Use |
|---|---|
| BST থেকে sorted value | Inorder |
| Copy / serialize / parent-আগে-ঠিক-করে | Preorder |
| Child-দের উত্তর parent-কে খাওয়ায় | Postorder |
| Per-level যেকোনো কিছু, বা nearest-first | Level order |
Part 2 — Tree problem patterns¶
Pattern A: Path problems¶
Trigger words: "root-to-leaf", "path sum", "all paths"।
Core idea: recursion-এর নিচে state বহন করো (remaining sum, path list)। Root-to-leaf path-এর প্রশ্ন তার condition check করে leaf-এ; path জমাতে গেলে লাগে ../06-recursion-and-backtracking/-এর choose/explore/un-choose শৃঙ্খলা — নামার পথে append, ফেরার পথে pop।
def has_path_sum(node, target):
if node is None:
return False
if node.left is None and node.right is None: # at a leaf:
return target == node.val # exact spend?
rest = target - node.val
return has_path_sum(node.left, rest) or has_path_sum(node.right, rest)
8/3/10 tree-তে dry run, target 12: 8 → child path-এ 4 দরকার → 3 → 1 দরকার → leaf 1 (1==1 হ্যাঁ)। Path 8→3→1 পাওয়া গেছে।
Problems: Path Sum https://leetcode.com/problems/path-sum/, Path Sum II https://leetcode.com/problems/path-sum-ii/।
Pattern B: Subtree problems¶
Trigger words: "same tree", "is subtree", "symmetric", "invert"।
Core idea: node-এর জোড়ার উপর recursion। দুটো tree মেলে যদি তাদের root মেলে এবং left মেলে left-এর সাথে এবং right মেলে right-এর সাথে (symmetry-র জন্য পাশগুলো mirror করো)। "S কি T-র subtree" = T-র প্রতিটা node-এ match-টা try করো।
def same(a, b):
if a is None and b is None:
return True
if a is None or b is None or a.val != b.val:
return False
return same(a.left, b.left) and same(a.right, b.right)
Problems: Same Tree https://leetcode.com/problems/same-tree/, Symmetric Tree https://leetcode.com/problems/symmetric-tree/, Subtree of Another Tree https://leetcode.com/problems/subtree-of-another-tree/, Invert Binary Tree https://leetcode.com/problems/invert-binary-tree/।
Pattern C: BST property exploitation¶
Trigger words: "BST", "sorted", "k-th smallest", "range", "closest value"।
Core idea: ordering-টা তোমাকে প্রতি comparison-এ পুরো একটা subtree ফেলে দিতে দেয় — search, insert, floor/ceiling সবই O(h)-এ চলে। Validation-কে BOUNDS নিচে পাঠাতেই হবে (প্রতিটা node তার ancestor-দের থেকে পাওয়া একটা interval-এ বাঁচে), কারণ property-টা পুরো subtree-কে বাঁধে:
def is_valid_bst(node, low=float("-inf"), high=float("inf")):
if node is None:
return True
if not (low < node.val < high):
return False
return (is_valid_bst(node.left, low, node.val) and
is_valid_bst(node.right, node.val, high))
বাঁয়ে গেলে ছাদটা নামে; ডানে গেলে মেঝেটা ওঠে। Children-only check (bounds ছাড়া) হলো সেই বিখ্যাত ভুল উত্তর।
Problems: Validate Binary Search Tree https://leetcode.com/problems/validate-binary-search-tree/, Search in a Binary Search Tree https://leetcode.com/problems/search-in-a-binary-search-tree/, Kth Smallest Element in a BST https://leetcode.com/problems/kth-smallest-element-in-a-bst/।
Pattern D: Lowest common ancestor (LCA)¶
Trigger words: "common ancestor", "meeting point", "distance between two nodes"।
Core idea: p আর q-র LCA হলো সবচেয়ে গভীর সেই node যার subtree-তে দুজনেই আছে — তাদের root-path-গুলো যেখানে আলাদা হয়, সেই কাঁটাচামচ-বিন্দু (FORK)।
BST-তে এটা চমৎকার সস্তা: root থেকে হাঁটো; দুটো target-ই ছোট হলে বাঁয়ে, দুটোই বড় হলে ডানে; প্রথম যে node তাদের মাঝে পড়ে (বা একটার সমান হয়) সেটাই fork:
def lca_bst(node, p, q):
if p.val < node.val and q.val < node.val:
return lca_bst(node.left, p, q)
if p.val > node.val and q.val > node.val:
return lca_bst(node.right, p, q)
return node # split point: one on each side (or node is p/q)
Dry run: 8/3/10 tree-তে LCA(1, 6) → 8-এ দুটোই < 8 → বাঁয়ে → 3-এ: 1 < 3 < 6 → split → উত্তর 3।
General binary tree-তে: postorder-style — প্রতিটা subtree-কে জিজ্ঞেস করো "তুমি কি p বা q পেয়েছ?"; প্রথম যে node-এর left এবং right দুটোই খুঁজে-পাওয়ার খবর দেয়, সেটাই LCA।
Problems: LCA of a BST https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/, LCA of a Binary Tree https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/।
Pattern E: Diameter via height — একটা জিনিস compute করো, আরেকটা update করো¶
Trigger words: "longest path", "diameter", "max path sum"।
Core idea: একটা node-এর ভেতর দিয়ে যাওয়া longest path = (left height + right height + 2)-টা edge। একটা postorder walk এমনিতেই height-গুলো bottom-up compute করে — তাই প্রতিটা call তার height RETURN করার পাশাপাশি একটা shared best-diameter-ও UPDATE করে। একটা traversal, দুটো কাজ।
def diameter(root):
best = [0]
def height(node):
if node is None:
return -1
lh = height(node.left)
rh = height(node.right)
best[0] = max(best[0], lh + rh + 2) # path bending at THIS node
return 1 + max(lh, rh) # but report only height upward
height(root)
return best[0]
8/3/10 tree-তে dry run: node 3-এ, lh=0 (1 থেকে), rh=0 (6 থেকে) → candidate 2; root 8-এ, lh=1, rh=1 → candidate 4 (path 1→3→8→10→14)। উত্তর 4।
এক-জিনিস-return / আরেক-জিনিস-record-এর এই ভাগটাই কঠিন tree interview-গুলোর signature চাল — Binary Tree Maximum Path Sum হুবহু এটাই, edge count-এর জায়গায় value বসিয়ে।
Problems: Diameter of Binary Tree https://leetcode.com/problems/diameter-of-binary-tree/, Binary Tree Maximum Path Sum https://leetcode.com/problems/binary-tree-maximum-path-sum/, CSES "Tree Diameter" — https://cses.fi/problemset/।
The inheritance map¶
recursion (../06-recursion-and-backtracking/)
│
▼
DFS trio: in / pre / post ──── stack version uses ../04-stack-and-queue/
│ │
│ └── postorder ──► height, subtree size ──► diameter ──► tree DP (CP)
│
├── inorder + BST property ──► sorted output, k-th smallest, validation bounds
│
└── path problems ──► choose/explore/un-choose on tree paths
queue (../04-stack-and-queue/) ──► level order ──► graph BFS (later sections)
পরের ধাপ: implementation.py চালাও, তারপর খোলো problems/README.md।