""" 07 - Trees: TreeNode, চারটা traversal-ই, measurement, আর একটা কাজ-করা BST। Contents: 1. TreeNode - building block-টা (value + left + right) 2. build_sample_tree - concept.md / visual-গুলোতে আঁকা সেই tree-টাই 3. inorder / preorder / postorder (recursive) 4. level_order - queue দিয়ে iterative BFS 5. inorder_iterative - explicit stack দিয়ে DFS (bonus) 6. height, count_nodes - bottom-up (postorder) computation-এর আদিরূপ 7. bst_insert / bst_search / is_valid_bst - BST trio শুধু standard library। চালাও: python implementation.py সব assert pass করতে হবে; demo traversal output-গুলো পাশাপাশি print করে। """ from collections import deque # --------------------------------------------------------------------- # 1. The node # --------------------------------------------------------------------- class TreeNode: """একটা node: একটা value আর দুটো child reference (None = missing child)।""" def __init__(self, val): self.val = val self.left = None self.right = None def __repr__(self): return f"TreeNode({self.val})" # --------------------------------------------------------------------- # 2. Sample tree (concept.md আর visual-explanation.md-র সেই একই tree) # --------------------------------------------------------------------- def build_sample_tree(): r"""এই BST-টা বানিয়ে ফেরত দেয়: 8 / \ 3 10 / \ \ 1 6 14 """ root = TreeNode(8) root.left = TreeNode(3) root.right = TreeNode(10) root.left.left = TreeNode(1) root.left.right = TreeNode(6) root.right.right = TreeNode(14) return root # --------------------------------------------------------------------- # 3. Depth-first trio (recursive) # একই হাঁটা; বদলায় শুধু value record করার মুহূর্তটা। # --------------------------------------------------------------------- def inorder(node, out=None): """Left -> Node -> Right। BST-তে এটা SORTED value দেয়।""" if out is None: out = [] if node is None: # base case: empty subtree কিছুই যোগ করে না return out inorder(node.left, out) out.append(node.val) # child-দের মাঝখানে visit inorder(node.right, out) return out def preorder(node, out=None): """Node -> Left -> Right। Parent আগে, descendant পরে: copy/serialize-এর order।""" if out is None: out = [] if node is None: return out out.append(node.val) # পৌঁছানোর মুহূর্তে visit preorder(node.left, out) preorder(node.right, out) return out def postorder(node, out=None): """Left -> Right -> Node। Child-রা আগে শেষ করে: compute/delete-এর order।""" if out is None: out = [] if node is None: return out postorder(node.left, out) postorder(node.right, out) out.append(node.val) # ছেড়ে যাওয়ার মুহূর্তে visit return out # --------------------------------------------------------------------- # 4. Level order (BFS) — iterative, queue-চালিত # --------------------------------------------------------------------- def level_order(root): """উপর থেকে নিচে, বাঁ থেকে ডানে, level ধরে ধরে grouped। Queue-টাই (FIFO, ../04-stack-and-queue/) পুরো কায়দা: child-রা পেছনে যোগ দেয়, তাই level k পুরো খালি হয় level k+1-এর আগে। `size = len(q)` ঠিক এক level-এর node-গুলোর snapshot নেয়। """ if root is None: return [] levels = [] q = deque([root]) while q: size = len(q) # এই মুহূর্তে q-তে যা আছে = এক 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 # --------------------------------------------------------------------- # 5. Bonus: explicit stack দিয়ে inorder (recursion ছাড়া) # --------------------------------------------------------------------- def inorder_iterative(root): """inorder()-এর সাথে একই output; stack-টা call stack-এর জায়গা নেয়। যত দূর সম্ভব বাঁয়ে slide করো (পথটা মনে রেখে), সবচেয়ে গভীর unvisited node-টা pop করো, record করো, তারপর তার right subtree-কেও একই treatment দাও। """ out, stack = [], [] node = root while node or stack: while node: # বাঁয়ে ডুব, ancestor-দের মনে রেখে stack.append(node) node = node.left node = stack.pop() # এখনো-visit-না-হওয়া সবচেয়ে গভীর node out.append(node.val) node = node.right # এবার তার ডান দিকটাও একই ডুব পায় return out # --------------------------------------------------------------------- # 6. Measurements — postorder-এর ভাবনা কাজে নেমেছে # --------------------------------------------------------------------- def height(node): """সবচেয়ে লম্বা নিচমুখী path-এর edge সংখ্যা। Empty tree = -1, single node = 0। খাঁটি postorder: আমার height-এর আগে দুই child-এর height থাকতেই হবে। """ if node is None: return -1 return 1 + max(height(node.left), height(node.right)) def count_nodes(node): """আমি + আমার বাঁয়ের সবাই + আমার ডানের সবাই।""" if node is None: return 0 return 1 + count_nodes(node.left) + count_nodes(node.right) # --------------------------------------------------------------------- # 7. BST operations # --------------------------------------------------------------------- def bst_insert(node, val): """val insert করো, (সম্ভবত নতুন) subtree root ফেরত দিয়ে। Search-এর মতোই নিচে হাঁটো; হাঁটাটা tree থেকে পড়ে গেলে সেখানেই node-টা বানাও। `node.left = bst_insert(...)`-এর এই re-linking style code-টাকে তিন লাইনে রাখে আর empty-tree case-টা ফ্রি-তে সামলায়। Duplicate-গুলো ignore করা হয় (একটা common সহজ policy)। """ if node is None: # tree থেকে পড়ে গেছি: এটাই জায়গা return TreeNode(val) if val < node.val: node.left = bst_insert(node.left, val) elif val > node.val: node.right = bst_insert(node.right, val) return node def bst_search(node, target): """target ধরে রাখা node-টা খোঁজো, না পেলে None। প্রতি level-এ এক comparison: O(h)।""" if node is None or node.val == target: return node if target < node.val: return bst_search(node.left, target) return bst_search(node.right, target) def is_valid_bst(node, low=float("-inf"), high=float("inf")): """সঠিক validation: প্রতিটা node-কে তার সব ancestor থেকে পাওয়া bounds মানতে হবে, শুধু parent-এরটা না। বাঁয়ে গেলে upper bound নেমে আসে node.val-এ। ডানে গেলে lower bound উঠে যায় node.val-এ। (শুধু children check করলে গভীরের violation ফসকে যায় - দেখো concept.md।) """ 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)) # --------------------------------------------------------------------- # Demo + tests # --------------------------------------------------------------------- if __name__ == "__main__": root = build_sample_tree() print("Sample tree: 8") print(" / \\") print(" 3 10") print(" / \\ \\") print(" 1 6 14\n") ino = inorder(root) pre = preorder(root) post = postorder(root) lvl = level_order(root) print(f"inorder : {ino} <- sorted, because it's a BST") print(f"preorder : {pre}") print(f"postorder : {post}") print(f"level order: {lvl}") # --- traversal correctness (visual-explanation.md-র সাথে হুবহু মেলে) --- assert ino == [1, 3, 6, 8, 10, 14] assert pre == [8, 3, 1, 6, 10, 14] assert post == [1, 6, 3, 14, 10, 8] assert lvl == [[8], [3, 10], [1, 6, 14]] assert inorder_iterative(root) == ino # stack version একমত assert ino == sorted(ino) # BST + inorder = sorted # --- empty আর single-node edge case --- assert inorder(None) == [] assert preorder(None) == [] assert postorder(None) == [] assert level_order(None) == [] assert inorder_iterative(None) == [] single = TreeNode(42) assert inorder(single) == [42] assert level_order(single) == [[42]] # --- measurements --- assert height(None) == -1 assert height(single) == 0 assert height(root) == 2 assert count_nodes(None) == 0 assert count_nodes(root) == 6 # --- BST: insertion দিয়ে নতুন একটা tree বানাও, তারপর কসরত করাও --- bst = None for v in [8, 3, 10, 1, 6, 14, 4, 7]: bst = bst_insert(bst, v) assert inorder(bst) == [1, 3, 4, 6, 7, 8, 10, 14] # সবসময় sorted assert count_nodes(bst) == 8 found = bst_search(bst, 6) assert found is not None and found.val == 6 assert bst_search(bst, 999) is None assert bst_search(bst, 1).val == 1 # একটা leaf-ও খুঁজে পাওয়া যায় bst = bst_insert(bst, 6) # duplicate: ignored assert count_nodes(bst) == 8 # --- BST validation, classic deep-violation ফাঁদটা সহ --- assert is_valid_bst(bst) is True assert is_valid_bst(root) is True assert is_valid_bst(None) is True # empty tree valid trap = TreeNode(8) # concept.md-র সেই ফাঁদ: trap.left = TreeNode(3) # 8 trap.right = TreeNode(10) # / \ trap.left.left = TreeNode(1) # 3 10 trap.left.right = TreeNode(9) # / \ # 9 > 3 (parent-child দেখতে ঠিক) কিন্তু 9 > 8 বসে # 1 9 <- bad! # আছে 8-এর LEFT subtree-তে -> BST না। assert is_valid_bst(trap) is False # degenerate chain-ও valid BST-ই (শুধু slow একটা) chain = None for v in [1, 2, 3, 4, 5]: chain = bst_insert(chain, v) assert is_valid_bst(chain) is True assert height(chain) == 4 # n-1 edges: O(n)-এর সতর্কবার্তা print("\nAll asserts passed. Tree toolkit verified.")