010 — Balanced Binary Tree¶
Source¶
- Original source: Classic tree height/balance exercise
- Platform: LeetCode — https://leetcode.com/problems/balanced-binary-tree/
- Topic: trees
- Difficulty: Easy
- Pattern: Height + verdict
- Basic idea inherited from: Maximum Depth, দুটো fact return করো — height হিসাব করার পাশাপাশি balanced কিনা সেটাও উপরে পাঠাও
1. Problem in simple words¶
তোমাকে একটা binary tree-র root দেওয়া আছে। তোমার কাজ: বলো tree-টা height-balanced কিনা — মানে প্রতিটা node-এ তার বাঁ-subtree আর ডান-subtree-র height-এর পার্থক্য 1-এর বেশি নয়।
2. Which basic idea does this inherit from?¶
এটা সরাসরি Maximum Depth (#1)-এর উপর দাঁড়ানো। সেখানে প্রতিটা node তার subtree-র height উপরে পাঠাত। এখানে প্রতিটা node দুটো fact একসাথে উপরে পাঠায়: (1) আমার height কত, আর (2) আমার subtree balanced কিনা। একটাই postorder traversal-এ দুই তথ্য fold করা — height-fold-এর একটা চালাক সম্প্রসারণ।
3. What is the hidden math or logic?¶
লুকানো logic হলো height আর verdict একসাথে bottom-up বহন করা:
check(empty) = (height = 0, balanced = True)
check(node):
(lh, lb) = check(node.left)
(rh, rb) = check(node.right)
balanced = lb and rb and abs(lh - rh) <= 1
height = 1 + max(lh, rh)
return (height, balanced)
মানে একটা node balanced তখনই যখন তার দুই subtree-ই balanced এবং তাদের height-এর পার্থক্য ≤ 1। height-এর হিসাব Maximum Depth-এর মতোই; শুধু পাশে একটা boolean যোগ হয়েছে।
4. Which data structure is needed?¶
কোনো extra data structure লাগে না। শুধু recursion call stack। প্রতিটা call দুটো মান (height ও balanced-flag) একটা tuple-এ মুড়ে উপরে ফেরায় — আলাদা কোনো container দরকার নেই।
5. Why this data structure fits¶
Tree self-similar (concept.md দেখো), আর "প্রতিটা node-এ যাচাই" মানে children-এর তথ্য দরকার — এটাই postorder। একটা recursive function দুই subtree-র (height, balanced) নিয়ে এসে এই node-এর জন্য combine করে। call stack bottom-up ফেরার পথটা মনে রাখে, তাই প্রতিটা node ঠিক একবার দেখা হয়।
6. Real-life analogy¶
একটা ঝুলন্ত mobile (শিশুর খেলনা যেটা ছাদ থেকে ঝোলে) ভাবো। পুরোটা ভারসাম্যপূর্ণ তখনই যখন প্রতিটা ছোট রড-এর দুই পাশ মোটামুটি সমান ঝুলছে — শুধু উপরেরটা না, প্রতিটা স্তরে। কোথাও এক পাশ অনেক বেশি ঝুলে গেলেই পুরো mobile কাত — গাছের একটা node-এ height-পার্থক্য 2 হয়ে গেলে যেমন।
7. Visual explanation¶
প্রতিটা node-এ (h, b) = (height, balanced); তথ্য নিচ থেকে উপরে ওঠে:
3 (h=3, b=True) |lh-rh|=|1-2|=1 ≤1 ✓
/ \
(1,True) 9 20 (h=2, b=True) |1-1|=0 ✓
/ \
(1,True)15 7 (1,True)
leaves → (1, True)
কোনো এক node-এ |lh-rh| > 1 হলে → সেখান থেকে b=False উপরে যায়
8. Example input and output¶
Input : root = [3,9,20,null,null,15,7] -> Output: True
Input : root = [1,2,2,3,3,null,null,4,4] -> Output: False (এক দিক গভীর)
Input : root = [] -> Output: True (খালি tree balanced)
Input : root = [1,2,null,3,null,4] -> Output: False (বাঁ-চেইন)
9. Brute force thinking¶
প্রথম সরল চিন্তা: প্রতিটা node-এ আলাদা করে দুই subtree-র height হিসাব করি (Maximum Depth-এর মতো), পার্থক্য ≤ 1 কিনা দেখি, তারপর সব node-এ এই চেক repeat করি।
1) প্রতিটা node visit করো
2) সেই node-এ left-height আর right-height আলাদা করে হিসাব করো
3) |left - right| > 1 হলে → False
4) সব node ঠিক থাকলে → True
10. Why brute force is slow¶
এই approach-এ প্রতিটা node-এ height হিসাব করতে গিয়ে তার নিচের পুরো subtree আবার ঘুরে আসা হয় — উপরের node-গুলোর জন্য নিচের অংশ বারবার ঘোরা হয়। তাই worst case O(n²) (চেইন tree-তে)। নিচের subtree-র height তো আগেই হিসাব হয়েছিল — সেটা ফেলে না দিয়ে উপরে নিয়ে গেলে পুরো কাজ একবারেই হয়।
11. Key observation¶
মূল observation: height আর "balanced কিনা" একই walk-এ একসাথে হিসাব করা যায়। আলাদা করে বারবার height মাপতে যেও না; প্রতিটা node থেকে height আর verdict — দুটো একসাথে উপরে পাঠাও। তাহলে প্রতিটা node ঠিক একবার দেখা হয়।
12. Optimized intuition¶
একটা postorder helper বানাও যেটা প্রতি node-এ (height, balanced) ফেরায়। দুই child থেকে এই জোড়া নাও; এই node balanced কিনা = দুই child balanced এবং abs(lh - rh) <= 1; height = 1 + max(lh, rh)। উপরে দুটোই পাঠাও। এক traversal, O(n)। (চাইলে balanced ভাঙা মাত্র height-এ একটা sentinel দিয়ে আগেই থামা যায়, কিন্তু tuple-version পরিষ্কার।)
13. Thinking tweak¶
মোচড়: "প্রতিটা node-এ height আলাদা করে মাপব" ভাবা বন্ধ করো — সেটাই O(n²)-এর ফাঁদ। বরং Maximum Depth-এর height-fold-টা নাও, আর তার পাশে আরেকটা fact (balanced?) একই return-এ গুঁজে দাও। "এক জিনিস হিসাব করতে করতে আরেকটা যাচাই" — এই দুই-fact return tree DP-র মূল চাল।
14. Step-by-step dry run¶
Input [1,2,null,3,null,4] (1→left 2→left 3→left 4, একটা বাঁ-চেইন):
- node 4 (leaf): (h=1, b=True)।
- node 3: left (1,True), right (0,True) → |1-0|=1 ≤1 → (h=2, b=True)।
- node 2: left (2,True), right (0,True) → |2-0|=2 > 1 → b=False, (h=3, b=False)।
- node 1: ডান (0,True), বাঁ (3,False) → child-এর b False → b=False → False।
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 is_balanced(root):
def check(node):
if node is None: # খালি subtree: height 0, balanced
return (0, True)
lh, lb = check(node.left) # বাঁ থেকে (height, balanced)
rh, rb = check(node.right) # ডান থেকে (height, balanced)
balanced = lb and rb and abs(lh - rh) <= 1 # এই node-এর verdict
height = 1 + max(lh, rh) # Maximum Depth-এর মতো height
return (height, balanced)
return check(root)[1] # শুধু balanced-flag ফেরাও
# ---- tests ----
assert is_balanced(build_tree([3, 9, 20, None, None, 15, 7])) is True
assert is_balanced(build_tree([1, 2, 2, 3, 3, None, None, 4, 4])) is False
assert is_balanced(build_tree([])) is True # খালি tree
assert is_balanced(build_tree([1, 2, None, 3, None, 4])) is False # বাঁ-চেইন
assert is_balanced(build_tree([1])) is True # একক node
print("সব test pass!")
16. Line-by-line code explanation¶
def check(node)— postorder helper; প্রতিটা node-এ(height, balanced)জোড়া ফেরায়।if node is None: return (0, True)— খালি subtree-র height 0, আর সেটা balanced।lh, lb = check(node.left)/rh, rb = check(node.right)— দুই child থেকে height ও balanced একসাথে নাও।balanced = lb and rb and abs(lh - rh) <= 1— মূল চাল: এই node balanced তখনই যখন দুই child balanced ও তাদের height-পার্থক্য ≤ 1।height = 1 + max(lh, rh)— Maximum Depth-এর height-fold।return check(root)[1]— পুরো হিসাব শেষে শুধু balanced-flag-টা চাই।
17. Output walkthrough¶
[3,9,20,null,null,15,7]: প্রতিটা node-এ height-পার্থক্য ≤ 1 → True। [1,2,2,3,3,null,null,4,4]: এক দিক বেশি গভীর → কোনো node-এ পার্থক্য 2 → False। খালি → True; [1,2,null,3,null,4] → False (dry run-এর সাথে মেলে); একক node → True। সব assert pass, শেষে print: সব test pass!।
18. Time complexity¶
O(n) — প্রতিটা node ঠিক একবার করে visit হয়, কারণ height নিচ থেকে উপরে নিয়ে যাওয়া হয় (পুনরায় হিসাব করা হয় না)। naive বারবার-height version হতো O(n²)।
19. Space complexity¶
O(h) — recursion call stack tree-র height h সমান গভীর হয়। balanced-এ O(log n), chain-এ O(n)। (concept.md-র table দেখো।) tuple ফেরানোয় বাড়তি জায়গা নগণ্য।
20. Common mistakes¶
- প্রতিটা node-এ আলাদা করে height মাপা → O(n²)। height উপরে নিয়ে যাও।
- শুধু root-এ পার্থক্য চেক করা → "প্রতিটা node-এ" শর্ত মিস; ভেতরের unbalanced ধরা পড়ে না।
<= 1-এর জায়গায়< 1লেখা → পার্থক্য ঠিক 1-ও ভুলভাবে unbalanced ধরা পড়ে।
21. Which basic problem this inherits from¶
ভিত্তি: Maximum Depth (#1)-র height-fold আর traversal-patterns.md-র postorder (children-before-parent)। height-fold-এর পাশে একটা boolean যোগ করলেই এই problem — concept.md-র height সংজ্ঞাও কাজে লাগে।
22. Similar harder problems¶
- Maximum Depth of Binary Tree (শুধু height, balanced ছাড়া) — https://leetcode.com/problems/maximum-depth-of-binary-tree/ (এই tracker-এর #1)
- Diameter of Binary Tree (height হিসাব করতে করতে পাশে diameter update) — https://leetcode.com/problems/diameter-of-binary-tree/ (#18)
- Binary Tree Maximum Path Sum (postorder-এ value-contribution fold) — https://leetcode.com/problems/binary-tree-maximum-path-sum/ (#23)
23. Pattern learned¶
Return-two-facts postorder: এক postorder walk-এ height (বা যেকোনো aggregate) আর একটা verdict একসাথে fold করে উপরে পাঠাও — এক traversal, O(n)। বারবার subtree মাপার O(n²) ফাঁদ এড়ানোর মূল কৌশল।
24. Final summary¶
ভবিষ্যতের আমাকে: "Balanced = প্রতিটা node-এ (height, balanced) জোড়া উপরে পাঠাও; balanced = দুই child balanced ও |lh-rh| ≤ 1।" "প্রতিটা node-এ যাচাই + height" দেখলেই এই দুই-fact postorder মনে পড়বে। মূল চাবি: height আলাদা করে বারবার মেপো না, একবারেই সাথে নিয়ে ওঠো।
মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।