အခန်း ၁၃ - Trees

အရင်အခန်းတွေမှာ data တွေကို Linear ပုံစံနဲ့ သိမ်းတာ များခဲ့ပါတယ် — Array (အခန်း ၃) က ဆက်တိုက်၊ Linked List (အခန်း ၈) က node တစ်ခုပြီးတစ်ခု၊ Stack/Queue (အခန်း ၇) ကလည်း တစ်ကြောင်းတည်း။ ဒါပေမယ့် real-world data အများစုက တန်းလျား မဟုတ်ဘဲ hierarchical ဖွဲ့စည်းပုံ ဖြစ်ပါတယ် —

• ကွန်ပျူတာ ထဲက folder တွေ — folder တစ်ခုထဲမှာ folder တွေ၊ file တွေ ပါသည်။
• ကုမ္ပဏီ တစ်ခုရဲ့ organization chart — CEO အောက်မှာ manager တွေ၊ သူတို့အောက်မှာ staff တွေ။
• E-commerce site ရဲ့ category — "Electronics" အောက်မှာ "Phone", "Laptop"; "Phone" အောက်မှာ brand တွေ။
• Facebook/Reddit ရဲ့ comment reply — comment တစ်ခုအောက်မှာ reply တွေ၊ reply အောက်မှာ ထပ် reply တွေ။

ဒီလို "တစ်ခုအောက်မှာ တစ်ခု ဆက်ခွဲ" ဖွဲ့စည်းပုံကို ကိုယ်စားပြုဖို့ Tree data structure ကို သုံးပါတယ်။ ဒီအခန်းမှာ Tree ဆိုတာ ဘာလဲ၊ ဝေါဟာရတွေ (node, root, leaf, height, depth)၊ Binary Tree၊ ပြီးတော့ Tree ကို ဖြတ်သန်း (traversal) ဖို့ နည်း ၄ မျိုး — Preorder, Inorder, Postorder, Level order — ကို လေ့လာသွားပါမယ်။ နောက်ဆုံးမှာ classic ပြဿနာ ၅ ခုကို တစ်ဆင့်ချင်း ဖြေရှင်းကြည့်ပါမယ်။

Tree ဆိုတာ ဘာလဲ

Tree ဆိုတာ node တွေကို parent-child (မိဘ-သားသမီး) ဆက်ဆံရေးနဲ့ ချိတ်ဆက်ထားတဲ့ data structure ဖြစ်ပါတယ်။ သစ်ပင် တစ်ပင်ကို မှောက်ထား သလို — အမြစ် (root) က အပေါ်မှာ၊ အကိုင်းအခက် (branch) တွေက အောက်ဘက် ဖြန့်သွားတယ်လို့ မြင်ရင် ရပါတယ်။

graph TD
    CEO[CEO] --> M1[Manager]
    CEO --> M2[Manager]
    M1 --> S1[Staff]
    M1 --> S2[Staff]
    M2 --> S3[Staff]

CEO = root (အမြစ်)，Staff တွေ = leaf (သားသမီး မရှိ)။

အဓိက ဝေါဟာရများ

Height နဲ့ Depth

Tree မှာ မကြာခဏ ရောထွေးတတ်တဲ့ ဝေါဟာရ ၂ ခုက height နဲ့ depth ဖြစ်ပါတယ် —

• Depth (အနက်) — root ကနေ အဲ့ node အထိ edge အရေအတွက်။ root ရဲ့ depth က 0။
• Height (အမြင့်) — အဲ့ node ကနေ အဝေးဆုံး leaf အထိ edge အရေအတွက်။ leaf ရဲ့ height က 0။
• Tree ၏ height — root ရဲ့ height (အနက်ဆုံး leaf ရဲ့ depth)။

graph TD
    A((A)) --> B((B))
    A --> C((C))
    B --> D((D))
    B --> E((E))

Tree height = 2 (A ကနေ D/E အထိ edge ၂ ခု)။ depth က အလွှာတူ node တိုင်း တူပေမယ့်၊ height က node တစ်ခုချင်း ကွဲသည် — ဥပမာ C က leaf ဖြစ်လို့ height = 0။

မှတ်ချက်: depth က "အပေါ်ကနေ ဘယ်လောက် နက်လဲ"၊ height က "အောက်ကို ဘယ်လောက် ကျန်သေးလဲ" လို့ မှတ်ရင် လွယ်ပါတယ်။ စာအုပ်/language အချို့မှာ edge အရေအတွက် မဟုတ်ဘဲ node အရေအတွက်နဲ့ ရေတွက်တာ ရှိလို့ (root depth = 1) သတိပြုပါ — ဒီစာအုပ်မှာ edge အရေအတွက်နဲ့ ရေတွက်ပါတယ်။

Binary Tree

Tree တစ်ခုမှာ node တစ်ခုစီ သားသမီး ဘယ်နှစ်ခု ရှိနိုင်လဲ ဆိုတာ ကန့်သတ်ချက် မရှိပါ (folder တစ်ခုထဲမှာ folder ၁၀ ခု ထားလို့ ရတယ်)။ ဒါပေမယ့် algorithm လေ့လာတဲ့အခါ အသုံးအများဆုံးက Binary Tree — node တစ်ခုစီမှာ children အများဆုံး ၂ ခု (left child, right child) ရှိတဲ့ tree ဖြစ်ပါတယ်။

graph TD
    N1((1)) --> N2((2))
    N1 --> N3((3))
    N2 --> N4((4))
    N2 --> N5((5))
    N3 --> N6((6))

node တစ်ခုစီမှာ left, right အများဆုံး ၂ ခုစီ။

Binary Tree node တစ်ခုကို code မှာ ဒီလို ဖော်ပြပါတယ် — Linked List (အခန်း ၈) က node နဲ့ ဆင်ပေမယ့် next တစ်ခုတည်း မဟုတ်ဘဲ left, right ၂ ခု ရှိတာ ကွာပါတယ် —

// Binary Tree node — value တစ်ခု + သားသမီး ၂ ခုဆီ link
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

Binary Tree အမျိုးအစားများ (အကြမ်းဖျင်း):

• Full — node တိုင်း သားသမီး 0 (သို့) 2 ခု ရှိ (၁ ခုတည်း မရှိ)။
• Complete — အလွှာတိုင်း အပြည့်၊ နောက်ဆုံး အလွှာသာ ဘယ်ကနေ ဖြည့် (Heap — အခန်း ၁၂ — ပုံစံ)။
• Balanced — ဘယ်/ညာ height ကွာဟမှု နည်း (search မြန်အောင်၊ အခန်း ၁၄ BST မှာ ဆက်လေ့လာရပါမယ်)။

Recursive Thinking

Tree ကို နားလည်ဖို့ အရေးကြီးဆုံး အချက်က — Tree ဟာ recursive structure ဖြစ်တာ ဖြစ်ပါတယ်။ node တစ်ခုရဲ့ left child ကိုယ်တိုင်က tree တစ်ခု (left subtree)၊ right child ကလည်း tree တစ်ခု (right subtree) ဖြစ်ပါတယ်။ ဒါကြောင့် Tree ပြဿနာ အများစုကို အခန်း ၁၀ က recursion နဲ့ ဖြေရှင်း နိုင်ပါတယ်။

Tree ပြဿနာ တွေးတဲ့ ပုံစံက အမြဲ တူပါတယ် —

1. Base case: node က null ဆိုရင် ဘာလုပ်မလဲ (များသောအားဖြင့် ရပ်)။
2. Recursive case: left subtree ကို ဖြေ၊ right subtree ကို ဖြေ၊ ပြီးတော့ လက်ရှိ node နဲ့ ပေါင်းစပ်။

solve(node):
    if node == null:  return base_value      ← base case
    left  = solve(node.left)                  ← left subtree ဖြေ
    right = solve(node.right)                 ← right subtree ဖြေ
    return combine(node, left, right)         ← ပေါင်းစပ်

ဒီ pattern ကို နားလည်ရင် Tree ပြဿနာ အများစုကို ဖြေနိုင်ပါပြီ။ အောက်က traversal တွေ၊ နောက်ပိုင်း ပြဿနာတွေ အကုန် ဒီ ပုံစံကနေ ဆင်းသက်လာတာ ဖြစ်ပါတယ်။

Tree Traversal

Traversal ဆိုတာ tree ထဲက node အားလုံးကို တစ်ခါ ဖြတ်သန်း (လည်ပတ်) ခြင်း ဖြစ်ပါတယ်။ Array ဆိုရင် ရှေ့ကနေ နောက် တန်းစီ ဖြတ်ရုံပါ။ ဒါပေမယ့် Tree က အကိုင်းအခက် ခွဲထားလို့ "ဘယ် node ကို အရင် ဖတ်မလဲ" ဆိုတဲ့ အစီအစဉ် အမျိုးမျိုး ရှိနိုင်ပါတယ်။

အဓိက ၂ မျိုး ရှိပါတယ် —

• DFS (Depth-First Search) — အကိုင်း တစ်ခုကို အောက်ဆုံး အထိ အရင် ဆင်းပြီးမှ ဘေး အကိုင်း ပြောင်း။ (recursion / stack နဲ့)
• BFS (Breadth-First Search) — အလွှာလိုက် (level order) — အပေါ်အလွှာ အကုန်ပြီးမှ အောက်အလွှာ။ (queue နဲ့)

DFS ကိုယ်တိုင် "လက်ရှိ node ကို ဘယ်အချိန် ဖတ်မလဲ" ပေါ်မူတည်ပြီး ၃ မျိုး ခွဲပါတယ် — Preorder, Inorder, Postorder။ အောက်က tree ကို ဥပမာ ထားပြီး ၄ မျိုးလုံး ကြည့်ရအောင် —

graph TD
    N1((1)) --> N2((2))
    N1 --> N3((3))
    N2 --> N4((4))
    N2 --> N5((5))

Preorder (Root → Left → Right)

လက်ရှိ node ကို အရင် ဖတ် ပြီးမှ left, right ဆင်းသည်။ Folder ထဲက file တွေ list လုပ်တာ၊ tree ကို copy/serialize လုပ်တာ မျိုးမှာ သုံးပါတယ်။

ဖတ်ပုံ:  1 → 2 → 4 → 5 → 3
        (root အရင်၊ ပြီးမှ ဘယ်ခြမ်း တစ်ခုလုံး၊ ပြီးမှ ညာခြမ်း)

void preorder(TreeNode node) {
    if (node == null) return;       // base case
    System.out.print(node.val + " ");  // 1. root ဖတ်
    preorder(node.left);            // 2. left subtree
    preorder(node.right);           // 3. right subtree
}

Inorder (Left → Root → Right)

ဘယ်ခြမ်း အရင်၊ ပြီးမှ လက်ရှိ node၊ ပြီးမှ ညာခြမ်း။

ဖတ်ပုံ:  4 → 2 → 5 → 1 → 3
        (node တစ်ခုရဲ့ ဘယ်ဘက် အကုန်ပြီးမှ သူ့ကိုယ်သူ၊ ပြီးမှ ညာဘက်)

void inorder(TreeNode node) {
    if (node == null) return;
    inorder(node.left);             // 1. left subtree
    System.out.print(node.val + " ");  // 2. root ဖတ်
    inorder(node.right);            // 3. right subtree
}

Postorder (Left → Right → Root)

children ၂ ခုလုံး အရင်၊ လက်ရှိ node ကို နောက်ဆုံး။ folder size တွက်တာ (children အကုန် တွက်ပြီးမှ ကိုယ်တိုင်)၊ tree ကို delete လုပ်တာ မျိုးမှာ သုံးပါတယ်။

ဖတ်ပုံ:  4 → 5 → 2 → 3 → 1
        (children အကုန်ပြီးမှ parent — root ကို နောက်ဆုံး)

void postorder(TreeNode node) {
    if (node == null) return;
    postorder(node.left);           // 1. left subtree
    postorder(node.right);          // 2. right subtree
    System.out.print(node.val + " ");  // 3. root ဖတ် (နောက်ဆုံး)
}

DFS ၃ မျိုး မှတ်နည်း: "Pre/In/Post" ဆိုတာ root ကို ဘယ်အချိန် ဖတ်လဲ ကို ဆိုလိုပါတယ် — Pre = root ကို အရင်၊ In = root ကို အလယ်, Post = root ကို နောက်ဆုံး။ left က right ထက် အမြဲ အရင် ဖြစ်ပါတယ်။

Level Order (BFS — အလွှာလိုက်)

DFS ၃ မျိုးက recursion (depth) နဲ့ ဆင်းတာ ဖြစ်ပြီး၊ Level Order ကတော့ အလွှာတစ်ခုလုံး ပြီးမှ နောက်အလွှာ ဖတ်တာ ဖြစ်ပါတယ်။ ဒါက Queue (အခန်း ၇) ကို သုံးပါတယ် — node တစ်ခု ဖတ်ပြီးတိုင်း childern တွေကို queue ထဲ ထည့်၊ queue ရှေ့ကနေ တစ်ခုချင်း ထုတ် ဖတ်သွားတာ ဖြစ်ပါတယ်။

ဖတ်ပုံ:  1 → 2 → 3 → 4 → 5
        (အလွှာ 0: [1]၊  အလွှာ 1: [2,3]၊  အလွှာ 2: [4,5])

import java.util.*;

void levelOrder(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);              // root ကို queue ထဲ ထည့်
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();    // ရှေ့ဆုံး ထုတ်
        System.out.print(node.val + " ");
        // သားသမီးတွေ queue ထဲ ထည့် (နောက်အလွှာ အတွက်)
        if (node.left != null)  queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}

DFS vs BFS ဘယ်အချိန် ဘာသုံးမလဲ:

• DFS (recursion) — code တို၊ "subtree တစ်ခုလုံး အဖြေ" လိုတဲ့ ပြဿနာ (depth, sum, path) တွေအတွက်။ tree အရမ်း နက်ရင် stack overflow (အခန်း ၁၀) ဖြစ်နိုင်ပါတယ်။
• BFS (queue) — "အလွှာလိုက်" အဖြေ (level order, အနီးဆုံး node, tree ၏ width) လိုရင်။ tree ကျယ်ရင် queue memory များနိုင်ပါတယ်။

Traversal Complexity: ၄ မျိုးလုံး node တိုင်းကို တစ်ခါစီ ဖတ်လို့ Time $O(n)$။ Space က DFS မှာ recursion stack အတွက် $O(h)$ ($h$ = tree height)၊ BFS မှာ queue အတွက် $O(w)$ ($w$ = တစ်အလွှာ၏ အများဆုံး node)။

Real-world Examples

Tree ဟာ "တစ်ခုအောက်မှာ တစ်ခု ဆက်ခွဲ" ဖွဲ့စည်းပုံ ရှိတဲ့ နေရာတိုင်းမှာ တွေ့ရပါတယ် —

• File System — folder အောက်မှာ folder/file တွေ။ folder size တွက်တာက postorder (သားသမီး အကုန် တွက်ပြီးမှ)။
• Category Tree — e-commerce ရဲ့ "Electronics → Phone → iPhone" မျိုး။ category page render လုပ်တာ preorder/level order။
• Menu Tree — app/website ရဲ့ navigation menu — submenu အောက်မှာ submenu။
• Comment Replies — comment အောက်က reply, reply အောက်က reply — recursion နဲ့ render။
• Organization Hierarchy — CEO → Manager → Staff။ "manager တစ်ယောက်အောက်က staff အကုန်" ရှာတာ subtree traversal။
• DOM Tree — HTML page ကိုယ်တိုင် Tree တစ်ခု — <html> root, အောက်မှာ <body>, <div> စသည်။

ဒီ pattern တွေ အကုန်လုံးက တူပါတယ် — node တစ်ခုကို ဖြေဖို့ သူ့သားသမီး (subtree) တွေ အရင် ဖြေပြီး ပေါင်းစပ် ဆိုတဲ့ recursive thinking ဖြစ်ပါတယ်။

Questions

Tree ကို လက်တွေ့ ပြဿနာ ၅ ခုနဲ့ ချိတ်ဆက် လေ့လာကြည့်ရအောင်။ ပြဿနာတိုင်းရဲ့ သော့ချက်က — အပေါ်က recursive thinking ("base case ဘာလဲ၊ subtree ၂ ခုကို ဘယ်လို ပေါင်းစပ်မလဲ") ကို မှန်ကန်စွာ ရှာတတ်ဖို့ ဖြစ်ပါတယ်။

၁။ Maximum Depth of Binary Tree

Binary tree တစ်ခုရဲ့ root ပေးထားသည်။ maximum depth (root ကနေ အဝေးဆုံး leaf အထိ node အရေအတွက်) ကို ပြန်ပါ။

Example 1:

graph TD
    N3((3)) --> N9((9))
    N3 --> N20((20))
    N20 --> N15((15))
    N20 --> N7((7))

Output: 3 — 3 → 20 → 15 (သို့ 7) — node ၃ ခု နက်သည်။

ရှင်းလင်းချက်

ဒါက recursive thinking ရဲ့ အသန့်ရှင်းဆုံး ဥပမာ ဖြစ်ပါတယ်။ node တစ်ခုရဲ့ depth ကို ဘယ်လို တွက်မလဲ?

• Base case: node က null ဆိုရင် depth = 0။
• Recursive case: လက်ရှိ node ရဲ့ depth = 1 + (left subtree, right subtree ၂ ခုထဲက ပိုနက်တာ)။

ဆိုလိုတာက "ကိုယ့်အောက်က ၂ ဘက်ထဲ ဘယ်ဘက် ပိုနက်လဲ ကြည့်၊ အဲ့ထဲ ကိုယ့်ကို ၁ ပေါင်း" ဆိုတဲ့ သဘောပါ။

Time Complexity: $O(n)$ - node တိုင်းကို တစ်ခါစီ။
Space Complexity: $O(h)$ - recursion stack ($h$ = height)။ အဆိုးဆုံး (skewed tree) $O(n)$။

Java Solution

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;             // base case
        int left = maxDepth(root.left);         // ဘယ်ခြမ်း depth
        int right = maxDepth(root.right);       // ညာခြမ်း depth
        return 1 + Math.max(left, right);       // ပိုနက်တာ + ကိုယ်တိုင်
    }
}

၂။ Invert Binary Tree

Binary tree တစ်ခုရဲ့ root ပေးထားသည်။ tree ကို ဘယ်/ညာ ပြောင်းပြန်လှန် (mirror) ပြီး root ကို ပြန်ပါ။

Example 1:

graph TD
    N4((4)) --> N2((2))
    N4 --> N7((7))
    N2 --> N1((1))
    N2 --> N3((3))
    N7 --> N6((6))
    N7 --> N9((9))

→ Output (ဘယ်/ညာ ပြန်လှန်):

graph TD
    N4((4)) --> N7((7))
    N4 --> N2((2))
    N7 --> N9((9))
    N7 --> N6((6))
    N2 --> N3((3))
    N2 --> N1((1))

ရှင်းလင်းချက်

"ပြောင်းပြန်လှန်" ဆိုတာ node တိုင်းရဲ့ left နဲ့ right ကို နေရာချင်း လဲ ဖို့ပါ။ recursive thinking နဲ့ —

• Base case: node က null ဆိုရင် ဘာမှ မလုပ်၊ null ပြန်။
• Recursive case: လက်ရှိ node ရဲ့ left, right ကို လဲ၊ ပြီးတော့ subtree ၂ ခုစလုံးကိုလည်း ပြန်လှန် (recursion)။

တစ်နည်းအားဖြင့် "ကိုယ့်သားသမီး ၂ ဦး လဲ၊ ပြီးတော့ သူတို့ကိုယ်စီကိုလည်း ပြန်လှန်ခိုင်း" ဆိုတဲ့ သဘောပါ။

Time Complexity: $O(n)$ - node တိုင်းကို တစ်ခါစီ။
Space Complexity: $O(h)$ - recursion stack။

Java Solution

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;          // base case
        // left, right လဲ
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        // subtree ၂ ခုကိုလည်း ပြန်လှန်
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

၃။ Same Tree

Binary tree ၂ ခု (p, q) ပေးထားသည်။ တူညီလား (structure တူ၊ value တူ) စစ်ပါ။

Example 1:

Input:    p:  1      q:  1
             / \        / \
            2   3      2   3
Output: true

Example 2:

Input:    p:  1      q:  1
             /            \
            2              2
Output: false  (structure မတူ — ဘယ်ဘက် vs ညာဘက်)

ရှင်းလင်းချက်

tree ၂ ခုကို တစ်ပြိုင်နက် ဖြတ်သန်းပြီး node တစ်ခုချင်း နှိုင်းယှဉ်ပါတယ်။

• Base case 1: node ၂ ခုလုံး null → ဒီနေရာ တူ (true)။
• Base case 2: တစ်ခုတည်း null (သို့) value မတူ → မတူ (false)။
• Recursive case: လက်ရှိ node တူရင်၊ left subtree ၂ ခု နဲ့ right subtree ၂ ခု စလုံး တူမှ true။

ဆိုလိုတာ "ကိုယ်တိုင်လည်း တူ၊ ဘယ်ခြမ်းလည်း တူ၊ ညာခြမ်းလည်း တူ" မှ tree တူတာ ဖြစ်ပါတယ်။

Time Complexity: $O(n)$ - node တိုင်းကို တစ်ခါစီ ($n$ = node အရေအတွက်)။
Space Complexity: $O(h)$ - recursion stack။

Java Solution

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;    // ၂ ခုလုံး null → တူ
        if (p == null || q == null) return false;   // တစ်ခုတည်း null → မတူ
        if (p.val != q.val) return false;           // value မတူ → မတူ
        // ကိုယ်တိုင်တူ → ဘယ်/ညာ ၂ ခုစလုံး တူမှ true
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

၄။ Binary Tree Level Order Traversal

Binary tree တစ်ခုရဲ့ root ပေးထားသည်။ node တွေကို အလွှာလိုက် (level order) — အလွှာတစ်ခုစီကို list ခွဲ — ပြန်ပါ။

Example 1:

graph TD
    N3((3)) --> N9((9))
    N3 --> N20((20))
    N20 --> N15((15))
    N20 --> N7((7))

Output: [[3], [9,20], [15,7]]

ရှင်းလင်းချက်

ဒါက အပေါ်က BFS (Queue) ကို တိုက်ရိုက် အသုံးချတာ ဖြစ်ပါတယ်။ ဒါပေမယ့် ဒီတစ်ခါ အလွှာတစ်ခုစီကို သီးခြား list အဖြစ် ခွဲ ပြန်ဖို့ လိုတယ်။

အဓိက လှည့်ကွက် — loop တစ်ပတ် မစခင် queue ထဲမှာ ရှိနေတဲ့ node အရေအတွက် (size) ကို မှတ်သည်။ အဲ့ size က လက်ရှိ အလွှာ၏ node အရေအတွက် အတိအကျ ဖြစ်ပါတယ်။ အဲ့ အရေအတွက်အတိုင်း ထုတ်ပြီး တစ်အလွှာ ပြီးအောင် လုပ်သည်။

• queue ထဲ root ထည့်။
• queue မဗလာမချင်း — လက်ရှိ size (အလွှာ node အရေအတွက်) ကို မှတ်၊ အဲ့ အရေအတွက်အတိုင်း node ထုတ်ပြီး တစ် list ထဲ စု၊ သားသမီးတွေ queue ထဲ ထည့်။

Time Complexity: $O(n)$ - node တိုင်းကို တစ်ခါစီ။
Space Complexity: $O(n)$ - queue နဲ့ result (အဆိုးဆုံး အလွှာတစ်ခုမှာ node $n/2$ ခန့်)။

Java Solution

import java.util.*;

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();              // လက်ရှိ အလွှာ node အရေအတွက်
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {      // ဒီ အလွှာအတွက်သာ
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null)  queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(level);                    // တစ်အလွှာ ပြီး
        }
        return result;
    }
}

၅။ Lowest Common Ancestor of a Binary Tree

Binary tree တစ်ခုနဲ့ node ၂ ခု (p, q) ပေးထားသည်။ သူတို့ ၂ ခုရဲ့ lowest common ancestor (LCA — အနိမ့်ဆုံး ဘုံ ဘိုးဘေး) ကို ပြန်ပါ။ LCA ဆိုတာ p နဲ့ q ၂ ခုလုံးကို subtree အဖြစ် ထိန်းထားတဲ့ အနက်ဆုံး node ဖြစ်ပါတယ်။

Example 1:

graph TD
    N3((3)) --> N5((5))
    N3 --> N1((1))
    N5 --> N6((6))
    N5 --> N2((2))

p = 6, q = 2 → Output: 5 (5 ၏ subtree ထဲ 6 နဲ့ 2 ၂ ခုလုံး ပါ)

ရှင်းလင်းချက်

ဒါက "comment thread ထဲ comment ၂ ခု ရဲ့ ဘုံ parent ရှာ" သို့ "folder ၂ ခု ရဲ့ ဘုံ folder ရှာ" မျိုး ပြဿနာ ဖြစ်ပါတယ်။ recursive thinking နဲ့ ရှင်းရှင်း ဖြေနိုင်ပါတယ် —

• Base case: node က null (သို့) p (သို့) q ဆိုရင် အဲ့ node ကို ပြန် (ဒီ subtree ထဲ ရှာတွေ့တဲ့ target)။
• Recursive case: left, right ၂ ဘက်မှာ ရှာ —
  • ၂ ဘက်စလုံး null မဟုတ် (target တစ်ခုစီ ၂ ဘက်မှာ ရှိ) → လက်ရှိ node ကိုယ်တိုင်က LCA။
  • တစ်ဘက်တည်းမှာ ရှိ → အဲ့ဘက်က ရလဒ်ကို အပေါ်ကို ပြန်တင်။

ဆိုလိုတာ — p နဲ့ q ၂ ခုက ကွဲ သွားတဲ့ နေရာ (node တစ်ခုက ဘယ်ဘက်၊ နောက်တစ်ခုက ညာဘက်) က LCA ဖြစ်ပါတယ်။

မှတ်ချက်: ဒါက သာမန် Binary Tree အတွက် နည်း ဖြစ်ပါတယ်။ Binary Search Tree (အခန်း ၁၄) ဆိုရင် "ဘယ်ငယ်၊ ညာကြီး" rule ကို သုံးပြီး ပိုလွယ်လွယ် ($O(h)$) ရှာနိုင်ပါတယ်။

Time Complexity: $O(n)$ - အဆိုးဆုံး node တိုင်းကို ဖတ်။
Space Complexity: $O(h)$ - recursion stack။

Java Solution

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // base case: null သို့ target တစ်ခု တွေ့
        if (root == null || root == p || root == q) return root;

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if (left != null && right != null) return root;  // ၂ ဘက်မှာ ကွဲ → ဒီ node က LCA
        return (left != null) ? left : right;             // တစ်ဘက်က ရလဒ် တင်
    }
}