005 — Invert Binary Tree

Source

• Original source: Classic binary tree manipulation exercise
• Platform: LeetCode — https://leetcode.com/problems/invert-binary-tree/
• Topic: trees
• Difficulty: Easy
• Pattern: Tree shape
• Basic idea inherited from: Swap + leap of faith — প্রতিটা node-এ দুই child swap করো, বাকিটা recursion-এর উপর বিশ্বাস

1. Problem in simple words

তোমাকে একটা binary tree-র root দেওয়া আছে। তোমার কাজ: পুরো tree-টাকে আয়নায় উল্টে দাও — মানে প্রতিটা node-এর বাঁ child আর ডান child জায়গা বদলে নেবে, পুরো গাছ জুড়ে। তারপর উল্টানো tree-র root ফেরত দাও।

   4              4
  / \            / \
 2   7   →      7   2
/ \ / \        / \ / \
1 3 6 9        9 6 3 1

2. Which basic idea does this inherit from?

এটা একটা সরল idea-র উপর দাঁড়ানো: swap + leap of faith। প্রতিটা node-এ শুধু তার দুই child-এর pointer অদলবদল করো, তারপর leap of faith নাও যে recursion বাকি দুই subtree-কেও নিজে নিজে উল্টে দেবে। Maximum Depth (#1)-এর মতোই — "নিজের কাজটুকু করো, child-দের বিশ্বাস করো।"

3. What is the hidden math or logic?

লুকানো logic হলো একটা recursive transformation:

invert(empty) = empty
invert(node)  = একটা node যার:
                    left  = invert(আগের right)
                    right = invert(আগের left)

মানে প্রতিটা subtree উল্টে যায়, আর তারপর দুই উল্টানো subtree-কে cross করে বসানো হয়। দুবার invert করলে আবার মূল tree ফিরে আসে — এটাই বলে দেয় operation-টা নিজের inverse।

4. Which data structure is needed?

কোনো extra data structure লাগে না। শুধু recursion call stack — tree-টা নিজেই data structure, আর আমরা সেটাকে জায়গায় বসেই (in-place) বদলাই। চাইলে recursion-এর বদলে একটা queue দিয়ে level-order ঘুরেও swap করা যায় (../../04-stack-and-queue/)।

5. Why this data structure fits

Tree self-similar (concept.md দেখো), তাই একটা recursive function নিখুঁত খাপ খায়: সে এক node-এর swap করে, তারপর নিজেকে দুই subtree-তে ডাকে। call stack এমনিতেই track রাখে কোন node-গুলো এখনো বাকি। কোনো নতুন node বানাতে হয় না — শুধু বিদ্যমান pointer অদলবদল।

6. Real-life analogy

একটা পরিবারের ছবি আয়নার সামনে ধরার কথা ভাবো। আয়নায় বাঁ দিকের সবাই ডানে চলে যায়, ডানের সবাই বাঁয়ে। শুধু উপরের স্তর না — প্রতিটা স্তরে, প্রতিটা ছোট দলেই বাঁ-ডান উল্টে যায়। পুরো ছবিটা একসাথে আয়নায় উল্টে গেলে যা হয়, ঠিক তাই।

7. Visual explanation

প্রতিটা node-এ আমরা তার দুই child swap করি; তারপর নিচে নেমে একই কাজ করি:

   4                    4   (swap 2 ও 7)
  / \                  / \
 2   7    swap→       7   2
/ \ / \              / \ / \
1 3 6 9             6 9 1 3   ← এখনো ভেতরের swap বাকি

প্রতিটা node-এ swap শেষ হলে:
   4
  / \
 7   2
/ \ / \
9 6 3 1

8. Example input and output

Input : root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Input : root = [2,1,3]   -> Output: [2,3,1]
Input : root = []        -> Output: []       (খালি tree)
Input : root = [1]       -> Output: [1]      (একটা node, কিছু বদলায় না)

9. Brute force thinking

প্রথম সরল চিন্তা: tree-টা যেকোনো order-এ পুরো ঘুরে আসি (যেমন level-order BFS), আর প্রতিটা node-এ পৌঁছে তার বাঁ ও ডান child swap করে দিই।

1) root একটা queue-তে রাখো
2) queue থেকে node বের করো, তার left ও right swap করো
3) তার (নতুন) দুই child queue-তে ঢোকাও
4) queue খালি হওয়া পর্যন্ত চালাও

10. Why brute force is slow

এই BFS version আসলে slow না — একই O(n), প্রতিটা node একবার করে swap হয়। শুধু একটা queue আলাদা করে maintain করতে হয়। recursion-এ সেই queue-র দরকার নেই; call stack নিজেই কাজটা করে দেয়, code ছোট ও পরিষ্কার থাকে। (BFS version-টা শুধু খুব গভীর tree-তে recursion limit এড়াতে কাজে লাগে।)

11. Key observation

মূল observation: প্রতিটা node-এ কাজ সম্পূর্ণ স্থানীয় (local) — শুধু তার নিজের দুই child swap করা। কোনো node-এর কাজ অন্য node-এর উপর নির্ভর করে না, তাই কোন order-এ ঘুরছি (pre/post/level) তাতে কিছু যায় আসে না — সবাই একবার করে swap পেলেই tree উল্টে যায়।

12. Optimized intuition

তিন ধাপের recursion: এই node-এর left ও right swap করো, তারপর নিজেকে নতুন left-এ ডাকো, নতুন right-এ ডাকো। base case-এ None হলে চুপচাপ ফিরে যাও। একবার পুরো tree ঘোরা — প্রতিটা node ঠিক একবার swap হয়।

13. Thinking tweak

মোচড়: "পুরো tree কীভাবে উল্টাব" — এই বড় প্রশ্ন ভাবা বন্ধ করো। বরং ভাবো "শুধু এই একটা node-এর দুই child পাল্টে দিই, আর ধরে নিই recursion বাকিটা সামলাবে।" বিশাল mirror-করা সমস্যা একটা ছোট, এক-লাইনের swap-এ গলে যায় — leap of faith-এর সবচেয়ে পরিষ্কার উদাহরণ।

14. Step-by-step dry run

Input [2,1,3] (root 2, left 1, right 3):

1. invert(2): 2-এর left(1) আর right(3) swap → এখন left=3, right=1।
2. invert(2.left = 3): 3 leaf, দুই child None, swap-এ কিছু হয় না → ফিরল।
3. invert(2.right = 1): 1 leaf, একই → ফিরল।
4. শেষ tree: root 2, left 3, right 1 → [2, 3, 1]।

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 level_order(root):
    """মিলিয়ে দেখার জন্য: tree-কে level-order list বানায় (trailing None ছাড়া)।"""
    if not root:
        return []
    out, q = [], deque([root])
    while q:
        node = q.popleft()
        if node is None:
            out.append(None)
            continue
        out.append(node.val)
        q.append(node.left)
        q.append(node.right)
    while out and out[-1] is None:   # শেষের অপ্রয়োজনীয় None ফেলে দাও
        out.pop()
    return out


def invert_tree(node):
    if node is None:                 # base case: খালি subtree
        return None
    node.left, node.right = node.right, node.left   # দুই child swap
    invert_tree(node.left)           # leap of faith: নতুন বাঁ-দিক উল্টে নেবে
    invert_tree(node.right)          # নতুন ডান-দিকও
    return node


# ---- tests ----
assert level_order(invert_tree(build_tree([4, 2, 7, 1, 3, 6, 9]))) == [4, 7, 2, 9, 6, 3, 1]
assert level_order(invert_tree(build_tree([2, 1, 3]))) == [2, 3, 1]
assert level_order(invert_tree(build_tree([]))) == []          # খালি tree
assert level_order(invert_tree(build_tree([1]))) == [1]        # একটা node
print("সব test pass!")

16. Line-by-line code explanation

• if node is None: return None — base case; খালি subtree-তে উল্টানোর কিছু নেই।
• node.left, node.right = node.right, node.left — মূল চাল: Python-এর tuple-swap দিয়ে এক লাইনে দুই pointer অদলবদল।
• invert_tree(node.left) — swap-এর পর যেটা এখন বাঁ-দিক, সেটাকেও উল্টে নাও (leap of faith)।
• invert_tree(node.right) — একই, নতুন ডান-দিকের জন্য।
• return node — উল্টানো subtree-র root ফেরত; root level-এ পুরো উল্টানো tree।
• level_order helper — শুধু test-এ tree-টা ঠিক উল্টেছে কিনা মিলিয়ে দেখতে।

17. Output walkthrough

[4,2,7,1,3,6,9] উল্টে হয় [4,7,2,9,6,3,1] (প্রতি level-এ বাঁ-ডান উল্টানো)। [2,1,3] → [2,3,1] (dry run-এর সাথে মেলে)। খালি tree → []; একক node → [1] (বদলায় না)। সব assert pass, শেষে print: সব test pass!।

18. Time complexity

O(n) — প্রতিটা node ঠিক একবার করে visit আর swap হয় (n = node সংখ্যা)।

19. Space complexity

O(h) — recursion call stack tree-র height h সমান গভীর হয়। balanced-এ O(log n), একপাশে ঝোলা chain-এ O(n)। (concept.md-র complexity table দেখো।) আলাদা tree বানাই না, তাই output-এর জন্য বাড়তি জায়গা লাগে না।

20. Common mistakes

• swap করার আগে child-এর reference হারিয়ে ফেলা (যেমন আলাদা লাইনে node.left = node.right করে দেওয়া, তারপর পুরোনো left হারিয়ে যায়) — tuple-swap এই ফাঁদ এড়ায়।
• base case ভুলে গিয়ে None.left ছোঁয়া → AttributeError।
• শুধু root level-এ swap করে recursion বাদ দেওয়া → শুধু উপরের স্তর উল্টায়, ভেতরটা না।

21. Which basic problem this inherits from

ভিত্তি: Maximum Depth (#1)-এর leap-of-faith recursion আর concept.md-র self-similar tree ধারণা। "এক node-এ local কাজ + দুই subtree-তে recurse" — এই কঙ্কালটাই এখানে swap দিয়ে ভরা।

22. Similar harder problems

• Symmetric Tree (একটা tree তার নিজের mirror কিনা যাচাই) — https://leetcode.com/problems/symmetric-tree/ (এই tracker-এর #7)
• Same Tree (দুই tree হুবহু এক কিনা) — https://leetcode.com/problems/same-tree/ (#6)
• Flatten Binary Tree to Linked List (tree-র shape pointer অদলবদল করে বদলানো) — https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

23. Pattern learned

Local-swap + recurse: প্রতিটা node-এ একটা ছোট স্থানীয় কাজ (এখানে child swap) করো, তারপর দুই subtree-তে নিজেকে ডাকো। কাজটা যেহেতু local, traversal order গুরুত্বপূর্ণ না — সবাই একবার করে পেলেই হলো।

24. Final summary

ভবিষ্যতের আমাকে: "invert = প্রতিটা node-এ left↔right swap, তারপর দুই দিকে recurse।" যখনই কোনো problem tree-র shape বদলাতে বলবে (mirror, swap, rearrange pointers), এই local-swap pattern মনে পড়বে। মূল মন্ত্র: এক node-এর কাজ করো, recursion-কে বাকিটার ভার দাও।

25. JavaScript solution (with test cases)

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

class TreeNode {
  constructor(val = 0, left = null, right = null) {
    this.val = val; this.left = left; this.right = right;
  }
}

function buildTree(values) {
  if (!values || values.length === 0) return null;
  const root = new TreeNode(values[0]);
  const q = [root];
  let i = 1, head = 0;
  while (head < q.length && i < values.length) {
    const node = q[head++];
    if (i < values.length && values[i] !== null) { node.left = new TreeNode(values[i]); q.push(node.left); }
    i++;
    if (i < values.length && values[i] !== null) { node.right = new TreeNode(values[i]); q.push(node.right); }
    i++;
  }
  return root;
}

// মিলিয়ে দেখার জন্য: tree-কে level-order array বানায় (শেষের null বাদ দিয়ে)
function levelOrder(root) {
  if (root === null) return [];
  const out = [], q = [root];
  let head = 0;
  while (head < q.length) {
    const node = q[head++];
    if (node === null) { out.push(null); continue; }
    out.push(node.val);
    q.push(node.left);
    q.push(node.right);
  }
  while (out.length && out[out.length - 1] === null) out.pop();
  return out;
}

function invertTree(node) {
  if (node === null) return null;                       // base case: খালি subtree
  [node.left, node.right] = [node.right, node.left];    // দুই child swap
  invertTree(node.left);                                // leap of faith: নতুন বাঁ-দিক
  invertTree(node.right);                               // নতুন ডান-দিকও
  return node;
}

const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);

// ---- test cases ----
assert(eq(levelOrder(invertTree(buildTree([4, 2, 7, 1, 3, 6, 9]))), [4, 7, 2, 9, 6, 3, 1]), "full");
assert(eq(levelOrder(invertTree(buildTree([2, 1, 3]))), [2, 3, 1]), "small");
assert(eq(levelOrder(invertTree(buildTree([]))), []), "খালি");
assert(eq(levelOrder(invertTree(buildTree([1]))), [1]), "একক node");
console.log("সব JS test pass!");

JS টীকা: Python-এর tuple-swap a, b = b, a-র সমতুল্য হলো JS-এর array destructuring [a, b] = [b, a] — এক লাইনে দুই pointer অদলবদল, কোনো temp variable ছাড়া, তাই পুরোনো reference হারানোর ফাঁদ এড়ায়। JSON.stringify দিয়ে level-order array তুলনা করি, কারণ JS-এ array সরাসরি === করা যায় না।

26. TypeScript solution (with test cases)

interface TreeNode { val: number; left: TreeNode | null; right: TreeNode | null; }

function node(val: number, left: TreeNode | null = null, right: TreeNode | null = null): TreeNode {
  return { val, left, right };
}

function buildTree(values: (number | null)[]): TreeNode | null {
  if (values.length === 0) return null;
  const root = node(values[0] as number);
  const q: TreeNode[] = [root];
  let i = 1, head = 0;
  while (head < q.length && i < values.length) {
    const cur = q[head++];
    if (i < values.length && values[i] !== null) { cur.left = node(values[i] as number); q.push(cur.left); }
    i++;
    if (i < values.length && values[i] !== null) { cur.right = node(values[i] as number); q.push(cur.right); }
    i++;
  }
  return root;
}

function levelOrder(root: TreeNode | null): (number | null)[] {
  if (root === null) return [];
  const out: (number | null)[] = [];
  const q: (TreeNode | null)[] = [root];
  let head = 0;
  while (head < q.length) {
    const cur = q[head++];
    if (cur === null) { out.push(null); continue; }
    out.push(cur.val);
    q.push(cur.left);
    q.push(cur.right);
  }
  while (out.length && out[out.length - 1] === null) out.pop();
  return out;
}

function invertTree(root: TreeNode | null): TreeNode | null {
  if (root === null) return null;
  [root.left, root.right] = [root.right, root.left];
  invertTree(root.left);
  invertTree(root.right);
  return root;
}

const expect = (cond: boolean, msg = ""): void => { if (!cond) throw new Error("FAIL " + msg); };
const eq = (a: (number | null)[], b: (number | null)[]): boolean =>
  a.length === b.length && a.every((v, i) => v === b[i]);

expect(eq(levelOrder(invertTree(buildTree([4, 2, 7, 1, 3, 6, 9]))), [4, 7, 2, 9, 6, 3, 1]), "full");
expect(eq(levelOrder(invertTree(buildTree([2, 1, 3]))), [2, 3, 1]), "small");
expect(eq(levelOrder(invertTree(buildTree([]))), []), "খালি");
expect(eq(levelOrder(invertTree(buildTree([1]))), [1]), "একক");
console.log("সব TS test pass!");

TS টীকা: levelOrder-এর return type (number | null)[] — কারণ output-এ value আর marker দুটোই থাকতে পারে; compiler নিশ্চিত করে আমরা দুটোই handle করছি। invertTree-এর TreeNode | null signature মনে করিয়ে দেয় base case (null) সামলাতেই হবে, তাই "শুধু root level swap করে recursion বাদ" ধরনের ভুল কম হয়।

27. কোথায় কাজে লাগে (real-world use)

• UI mirroring (RTL layout): আরবি/হিব্রু-র মতো right-to-left ভাষার জন্য একটা layout tree আয়নায় উল্টে দেওয়া — বাঁ আর ডান child swap করাই মূল কাজ।
• Image / matrix transformation: ছবি horizontally flip করা বা binary space partition tree mirror করা গ্রাফিক্স pipeline-এ একই pointer-swap pattern।
• Game tree symmetry: দাবা/গো-র মতো খেলায় একটা position-এর mirror version তৈরি করা (board symmetry কাজে লাগিয়ে search ছোট করতে)।
• Refactoring / AST transformation: কোনো expression-এ commutative operator-এর দুই পাশ swap করে normalize করা — compiler optimization-এ।
• Test fixture generation: একটা পরিচিত tree-র mirror বানিয়ে symmetry-জাতীয় algorithm (যেমন Symmetric Tree #7) test করা।

মূল সুর: যখনই কোনো hierarchical structure-কে আয়নায় উল্টাতে হবে (বাঁ↔ডান), এই local-swap + recurse pattern-ই সবচেয়ে ছোট ও পরিষ্কার সমাধান।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।