အခန်း ၁၄ - Binary Search Tree

အခန်း ၁၃ မှာ Binary Tree ဆိုတာ node တစ်ခုစီ သားသမီး အများဆုံး ၂ ခု (left, right) ရှိတဲ့ tree ဖြစ်တာ၊ ပြီးတော့ traversal နည်း ၄ မျိုးကို လေ့လာခဲ့ပါတယ်။ ဒါပေမယ့် သာမန် Binary Tree မှာ node တွေရဲ့ တန်ဖိုး (value) တွေက အစီအစဉ် မရှိပါ — တန်ဖိုး x ရှိမရှိ ရှာဖို့ tree တစ်ခုလုံး ( $n$ node) ဖြတ်ရလို့ $O(n)$ ကုန်ပါတယ်။

အခန်း ၃ က Binary Search ကို ပြန်စဉ်းစားကြည့်ရအောင် — sorted array မှာ အလယ်ကို ကြည့်ပြီး "ရှာတဲ့ဟာ ပိုကြီးလား ပိုငယ်လား" အလိုက် တစ်ဝက် ဖြတ်ပစ်လို့ $O(\log n)$ နဲ့ ရှာနိုင်ခဲ့ပါတယ်။ ဒီ "တစ်ဝက် ဖြတ်ပစ်" idea ကို Tree ပေါ်မှာ တင်လိုက်ရင် ဘာဖြစ်မလဲ?

အဲ့ဒါက Binary Search Tree (BST) ဖြစ်ပါတယ် — "ဘယ်ငယ်၊ ညာကြီး" ဆိုတဲ့ စည်းမျဉ်း တစ်ခု ထည့်ထားတဲ့ Binary Tree ဖြစ်ပြီး၊ search/insert/delete တွေကို ပျမ်းမျှ $O(\log n)$ နဲ့ လုပ်နိုင်ပါတယ်။ ဒီအခန်းမှာ BST ဆိုတာ ဘာလဲ၊ "ဘယ်ငယ်၊ ညာကြီး" rule က ဘာကြောင့် search မြန်စေသလဲ၊ insert/delete ဘယ်လို လုပ်လဲ၊ balance ပျက်ရင် ဘာဖြစ်လဲ ဆိုတာတွေ လေ့လာပြီး၊ classic ပြဿနာ ၅ ခုကို တစ်ဆင့်ချင်း ဖြေရှင်းကြည့်ပါမယ်။

Binary Search Tree ဆိုတာ ဘာလဲ

Binary Search Tree (BST) ဆိုတာ node တိုင်းမှာ ဒီ စည်းမျဉ်း ပြည့်ရတဲ့ Binary Tree ဖြစ်ပါတယ် —

ဘယ် subtree ထဲက node အားလုံးရဲ့ တန်ဖိုးက လက်ရှိ node ထက် ငယ် ရမည်။
ညာ subtree ထဲက node အားလုံးရဲ့ တန်ဖိုးက လက်ရှိ node ထက် ကြီး ရမည်။
ဘယ်/ညာ subtree ၂ ခုစလုံးကိုယ်တိုင်လည်း BST ဖြစ်ရမည် (recursive)။

အတိုချုံး "ဘယ်ငယ်၊ ညာကြီး" လို့ မှတ်ပါ။ ဒီ rule ပြည့်တဲ့ BST တစ်ခု ကြည့်ရအောင် —

graph TD
    N8((8)) --> N3((3))
    N8 --> N10((10))
    N3 --> N1((1))
    N3 --> N6((6))
    N10 --> N14((14))
    N6 --> N4((4))
    N6 --> N7((7))
    N14 --> N13((13))

8 (root): ဘယ်ဘက် (3,1,6,4,7) အကုန် < 8၊ ညာဘက် (10,14,13) အကုန် > 8
3: ဘယ် (1) < 3 < ညာ (6,4,7)
10: ညာ (14,13) > 10

သတိ — Heap နဲ့ မရောထွေးပါနဲ့: အခန်း ၁၂ က Heap မှာ "မိဘ-သားသမီး" ဆက်ဆံရေးကိုသာ ထိန်းပြီး ဘေးချင်းကပ် (sibling) တွေကြား အစီအစဉ် မရှိပါ။ BST မှာတော့ node အားလုံး "ဘယ်ငယ်၊ ညာကြီး" အစီအစဉ်တကျ ရှိလို့ "တန်ဖိုး x ရှိလား" ကို မြန်မြန် ရှာနိုင်ပါတယ်။ Heap က "အကြီး/အငယ်ဆုံး" ထုတ်ဖို့ ကောင်းပြီး၊ BST က "ရှာဖို့/စီထားဖို့" ကောင်းပါတယ်။

BST node ကို code မှာ ဖော်ပြတာ အခန်း ၁၃ က TreeNode အတိုင်းပါပဲ —

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

"ဘယ်ငယ်၊ ညာကြီး" rule က ဘာကြောင့် မြန်သလဲ

BST ရဲ့ အသက်က — node တစ်ခုကို ရောက်တိုင်း ရှာတဲ့ တန်ဖိုးနဲ့ နှိုင်းယှဉ်ပြီး ဘယ် (သို့) ညာ တစ်ဘက်ကို ဆင်း လို့ ရတာ ဖြစ်ပါတယ်။ ဒါက Binary Search (အခန်း ၃) က "အလယ်ကို ကြည့်ပြီး တစ်ဝက် ဖြတ်ပစ်" တာနဲ့ အတိအကျ တူပါတယ် —

ရှာတဲ့ တန်ဖိုးက လက်ရှိ node ထက် ငယ် ရင် → ဘယ်ဘက် ဆင်း (ညာဘက် တစ်ခုလုံး မလို)။
ကြီး ရင် → ညာဘက် ဆင်း (ဘယ်ဘက် တစ်ခုလုံး မလို)။
တူ ရင် → တွေ့ပြီ။

အဆင့်တိုင်းမှာ subtree တစ်ခု (node တစ်ဝက်) ကို လုံးဝ ဖြတ်ပစ်လို့၊ tree က balance ဖြစ်ရင် အဆင့် $\log n$ ခုသာ ဆင်းရပါတယ်။ အပေါ်က tree မှာ 7 ကို ရှာကြည့်ရအောင် —

ရှာ: 7
  8 မှာ — 7 < 8 → ဘယ်ဆင်း     (10, 14, 13 ... တစ်ဝက် ဖြတ်)
  3 မှာ — 7 > 3 → ညာဆင်း     (1 ဖြတ်)
  6 မှာ — 7 > 6 → ညာဆင်း
  7 မှာ — 7 == 7 → တွေ့ပြီ ✓

   node ၄ ခုသာ ကြည့်ရ (tree မှာ node ၉ ခု ရှိ)

// BST ထဲ target ရှိမရှိ ရှာ (iterative)
boolean search(TreeNode root, int target) {
    TreeNode node = root;
    while (node != null) {
        if (target == node.val) return true;     // တွေ့ပြီ
        else if (target < node.val) node = node.left;   // ငယ် → ဘယ်
        else node = node.right;                  // ကြီး → ညာ
    }
    return false;                                // ကုန်တဲ့အထိ မတွေ့
}

Complexity: search က tree ရဲ့ အမြင့် ( $h$ ) အတိုင်းသာ ဆင်းရလို့ $O(h)$ ဖြစ်ပါတယ်။ tree က balance ဖြစ်ရင် $h \approx \log n$ ဖြစ်လို့ $O(\log n)$ ။ (balance ပျက်ရင် ဘာဖြစ်လဲ နောက်မှာ ကြည့်ပါမယ်။)

Inorder Traversal

အခန်း ၁၃ က Inorder traversal (Left → Root → Right) ကို မှတ်မိမယ် ထင်ပါတယ်။ BST တစ်ခုကို Inorder ဖြတ်ရင် တန်ဖိုးတွေ စီပြီးသား (sorted, ငယ်→ကြီး) ထွက်လာ တာ ဖြစ်ပါတယ် — ဒါက BST ရဲ့ အရေးကြီးဆုံး ဂုဏ်သတ္တိ ဖြစ်ပါတယ်။

ဘာကြောင့်လဲ? Inorder က node တစ်ခုစီမှာ "ဘယ်ဘက် (ပိုငယ်တာတွေ) အရင်၊ ပြီးမှ ကိုယ်တိုင်၊ ပြီးမှ ညာဘက် (ပိုကြီးတာတွေ)" ဖတ်တာ ဖြစ်လို့ — "ဘယ်ငယ်၊ ညာကြီး" rule နဲ့ ပေါင်းလိုက်ရင် ငယ်ရာက ကြီးရာ အစီအစဉ်အတိုင်း ထွက်လာတာ ဖြစ်ပါတယ်။

graph TD
    N8((8)) --> N3((3))
    N8 --> N10((10))
    N3 --> N1((1))
    N3 --> N6((6))
    N10 --> N14((14))

Inorder: 1 → 3 → 6 → 8 → 10 → 14 (စီပြီးသား!)

// BST ကို inorder ဖြတ်ရင် sorted ထွက်
void inorder(TreeNode node, List<Integer> result) {
    if (node == null) return;
    inorder(node.left, result);     // ဘယ် (ပိုငယ်) အရင်
    result.add(node.val);           // ကိုယ်တိုင်
    inorder(node.right, result);    // ညာ (ပိုကြီး) နောက်ဆုံး
}

အသုံးဝင်ပုံ: ဒီ ဂုဏ်သတ္တိကြောင့် "BST ကို sorted list ပြောင်း", "kth smallest ရှာ", "BST မှန်မမှန် စစ်" စတဲ့ ပြဿနာ အများစုကို Inorder နဲ့ ဖြေနိုင်ပါတယ်။ နောက်က Questions မှာ ဒါကို သုံးပါမယ်။

Insert — node အသစ် ထည့်ခြင်း

BST ထဲ တန်ဖိုး အသစ် တစ်ခု ထည့်တဲ့အခါ — search လုပ်သလိုပဲ "ဘယ်ငယ်၊ ညာကြီး" အလိုက် ဆင်းသွား ပြီး၊ နေရာလွတ် (null) ရောက်တဲ့အခါ အဲ့မှာ ချသည်။ ဒါက rule ကို မပျက်စေဘဲ မှန်ကန်တဲ့ နေရာ အလိုအလျောက် ရှာပေးပါတယ်။

[8, 3, 10, 1, 6, 14] BST ထဲ 5 ထည့်ကြည့်ရအောင် —

ထည့်: 5
  8 မှာ — 5 < 8 → ဘယ်ဆင်း
  3 မှာ — 5 > 3 → ညာဆင်း
  6 မှာ — 5 < 6 → ဘယ်ဆင်း
  6 ရဲ့ ဘယ်ဘက် null → ဒီမှာ ချ

              8                    8
            /   \                /   \
           3     10     →       3     10
          / \      \           / \      \
         1   6      14        1   6      14
                                 /
                                5   ← အသစ်

// BST ထဲ value ထည့်ပြီး root ပြန်ပေး (recursive)
TreeNode insert(TreeNode root, int value) {
    if (root == null) return new TreeNode(value);   // နေရာလွတ် → ဒီမှာ ချ
    if (value < root.val) {
        root.left = insert(root.left, value);        // ငယ် → ဘယ်ဘက် ထည့်
    } else if (value > root.val) {
        root.right = insert(root.right, value);      // ကြီး → ညာဘက် ထည့်
    }
    // value == root.val ဆိုရင် (ထပ်) ဘာမှ မလုပ် — BST မှာ duplicate မထား
    return root;
}

Complexity: insert ကလည်း မှန်ကန်တဲ့ နေရာ ရှာဖို့ tree ရဲ့ အမြင့်အတိုင်း ဆင်းရလို့ $O(h)$ (balance ဖြစ်ရင် $O(\log n)$ ) ဖြစ်ပါတယ်။

Delete — node ဖျက်ခြင်း (အခက်ဆုံး operation)

BST ထဲက node ဖျက်တာက အခက်ဆုံး operation ဖြစ်ပါတယ် — ဖျက်ပြီးနောက် "ဘယ်ငယ်၊ ညာကြီး" rule မပျက်အောင် ထိန်းရတဲ့အတွက် ဖြစ်ပါတယ်။ ဖျက်မယ့် node ကို ရှာတွေ့ပြီးတဲ့အခါ အခြေအနေ ၃ မျိုး ရှိပါတယ် —

အခြေအနေ ၁ — leaf (သားသမီး မရှိ): တိုက်ရိုက် ဖျက်ပစ်ရုံ (null ပြန်)။

   1 ကို ဖျက်:        3              3
                     / \      →      \
                    1   6             6

အခြေအနေ ၂ — သားသမီး ၁ ခု: အဲ့ node နေရာကို သူ့ သားသမီး တစ်ခုတည်းနဲ့ အစားထိုးရုံ။

   10 ကို ဖျက်:      10             14
                       \      →
                       14

အခြေအနေ ၃ — သားသမီး ၂ ခု: ဒါက အခက်ဆုံး။ အဲ့ node ကို ဖျက်ပေမယ့် rule မပျက်အောင် — ညာ subtree ထဲက အငယ်ဆုံး node (inorder successor) ကို ရှာ၊ အဲ့ တန်ဖိုးကို ဖျက်မယ့် node ပေါ် ကူးထည့်၊ ပြီးတော့ အဲ့ successor ကို ညာ subtree ထဲကနေ ဖျက်ပစ်သည်။

ဘာကြောင့် "ညာဘက်က အငယ်ဆုံး" လဲ? ဒါက ဖျက်မယ့် node ထက် ကြီးတဲ့ တန်ဖိုးတွေထဲ အငယ်ဆုံး ဖြစ်လို့ — အဲ့ နေရာ တင်ရင် ဘယ်ဘက် (အကုန် ပိုငယ်) ရော ညာဘက် (ကျန်တာ ပိုကြီး) ရော rule မပျက်ပါ။

   3 ကို ဖျက် (သား ၂ ခု: 1, 6):

              8                         8
            /   \                     /   \
           3     10        →         4     10      ← 3 နေရာမှာ 4 (ညာဘက်က အငယ်ဆုံး)
          / \                       / \
         1   6                     1   6
            /                            (4 ကို မူရင်းနေရာက ဖျက်)
           4

TreeNode delete(TreeNode root, int value) {
    if (root == null) return null;

    if (value < root.val) {
        root.left = delete(root.left, value);        // ဘယ်ဘက်မှာ ရှာ
    } else if (value > root.val) {
        root.right = delete(root.right, value);      // ညာဘက်မှာ ရှာ
    } else {
        // တွေ့ပြီ — အခြေအနေ ၃ မျိုး
        if (root.left == null) return root.right;    // သား ၀/၁ (ဘယ်မရှိ)
        if (root.right == null) return root.left;    // သား ၁ (ညာမရှိ)

        // သား ၂ ခု — ညာဘက်က အငယ်ဆုံး (inorder successor) ရှာ
        TreeNode successor = root.right;
        while (successor.left != null) successor = successor.left;
        root.val = successor.val;                    // တန်ဖိုး ကူး
        root.right = delete(root.right, successor.val);  // successor ကို ဖျက်
    }
    return root;
}

Complexity: delete ကလည်း node ရှာ + successor ရှာ — ၂ ခုစလုံး tree အမြင့်အတိုင်း ဖြစ်လို့ $O(h)$ ဖြစ်ပါတယ်။

Balance ပျက်ရင် ဘာဖြစ်လဲ — BST ၏ အားနည်းချက်

BST ရဲ့ operation အကုန်လုံး $O(h)$ (tree အမြင့်) ဖြစ်တာ သတိထားမိမယ် ထင်ပါတယ်။ tree က balance ဖြစ်ရင် $h \approx \log n$ ဖြစ်လို့ $O(\log n)$ — အရမ်းမြန်ပါတယ်။ ဒါပေမယ့် balance ပျက်ရင် $h$ က $n$ အထိ ကြီးနိုင်ပါတယ်။

ဥပမာ — စီပြီးသား data [1, 2, 3, 4, 5] ကို အစဉ်လိုက် insert လုပ်ရင် ဘာဖြစ်လဲ?

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

node တိုင်း ညာဘက်ပဲ ဆင်း — ဒါက Linked List (အခန်း ၈) နဲ့ အတူတူ! h = n

ဒီ "skewed (တစ်ဘက်စောင်း) tree" မှာ search/insert/delete အကုန် $O(n)$ ဖြစ်သွားပါတယ် — BST ရဲ့ အားသာချက် ပျောက်သွားပါတယ်။

Tree အခြေအနေ	အမြင့် $h$	Search/Insert/Delete
Balanced (ညီညာ)	$O(\log n)$	$O(\log n)$ ⚡
Skewed (တစ်ဘက်စောင်း)	$O(n)$	$O(n)$ 🐢

ဖြေရှင်းနည်း — Self-balancing BST: ဒီ ပြဿနာကို ဖြေဖို့ insert/delete လုပ်တိုင်း tree ကို အလိုအလျောက် balance ပြန်ညှိ တဲ့ BST မျိုး ရှိပါတယ် — AVL Tree, Red-Black Tree စသည်။ ဒါတွေက balance ကို အမြဲ ထိန်းလို့ အဆိုးဆုံးမှာတောင် $O(\log n)$ အာမခံပါတယ်။ (Java ရဲ့ TreeMap/TreeSet, C++ ရဲ့ std::map တွေက Red-Black Tree နဲ့ လုပ်ထားတာ ဖြစ်ပါတယ်။) ဒီစာအုပ်မှာ self-balancing ရဲ့ အသေးစိတ်ကို မလေ့လာပေမယ့်၊ "လက်တွေ့မှာ ဒီ data structure တွေ သုံးတယ်" ဆိုတာ မှတ်ထားပါ။

Real-world Examples

BST (နဲ့ သူ့ self-balancing မျိုးကွဲတွေ) ဟာ "data ကို စီထားပြီး အမြန် ရှာ/ထည့်/ဖျက်" လိုတဲ့ နေရာတိုင်းမှာ တွေ့ရပါတယ် —

Database Index — database က row တွေကို အမြန် ရှာဖို့ index ကို B-Tree / B+ Tree (BST နဲ့ ဆင်တဲ့ multi-way ordered search tree — binary မဟုတ်) နဲ့ သိမ်းသည်။ "WHERE age > 30" မျိုး range query မြန်စေသည်။
Map / Set (Sorted) — Java TreeMap/TreeSet, C++ std::map — key တွေကို စီပြီးသား ထားရင်း $O(\log n)$ ရှာ/ထည့်/ဖျက်။
Auto-complete / Dictionary — စာလုံး တစ်ခု ရိုက်တိုင်း "ဒီ prefix နဲ့ စတဲ့ စကားလုံးတွေ" ကို sorted order နဲ့ ပြ။
Range Query — "ဈေးနှုန်း ၁၀၀၀ နဲ့ ၅၀၀၀ ကြား product တွေ" မျိုး — BST မှာ ဒီ range ကို မြန်မြန် ဖြတ်ထုတ်နိုင်။
Scheduling / Calendar — event တွေကို အချိန်အလိုက် စီထား၊ "နောက်ထပ် event ဘယ်အချိန်လဲ" အမြန် ရှာ။

ဒီ pattern တွေ အကုန်လုံးက တူပါတယ် — "data ကို စီထားရင်း၊ ရှာ/ထည့်/ဖျက် ၃ ခုစလုံးကို မကြာခဏ လုပ်ရတယ်" ဆိုတဲ့ အခြေအနေပါ။ Sorted Array က ရှာတာ မြန်ပေမယ့် ထည့်/ဖျက်တာ $O(n)$ (shift လုပ်ရ)၊ Hash Map (အခန်း ၄) က ရှာ/ထည့်/ဖျက် မြန်ပေမယ့် အစီအစဉ် မရှိ — BST က ၃ ခုစလုံး $O(\log n)$ နဲ့ အစီအစဉ်ပါ ထိန်းပေးတာ ဖြစ်ပါတယ်။

Questions

BST ကို လက်တွေ့ ပြဿနာ ၅ ခုနဲ့ ချိတ်ဆက် လေ့လာကြည့်ရအောင်။ ပြဿနာတိုင်းရဲ့ သော့ချက်က — "ဘယ်ငယ်၊ ညာကြီး" rule (နဲ့ inorder က sorted ထွက်တာ) ကို အသုံးချပြီး tree တစ်ဝက် ဖြတ်ပစ်တတ်ဖို့ ဖြစ်ပါတယ်။

၁။ Search in a Binary Search Tree

BST တစ်ခုရဲ့ root နဲ့ ကိန်း val ပေးထားသည်။ တန်ဖိုး val ရှိတဲ့ node ကို ရှာ၊ အဲ့ node ကို root ဖြစ်တဲ့ subtree ကို ပြန်ပါ။ မရှိရင် null ပြန်ပါ။

Example 1:

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

val = 2 → Output: node 2 ၏ subtree (2, 1, 3)

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

ဒါက အပေါ်က search ကို တိုက်ရိုက် အသုံးချတာ ဖြစ်ပါတယ်။ "ဘယ်ငယ်၊ ညာကြီး" rule နဲ့ —

val က လက်ရှိ node ထက် ငယ် ရင် → ဘယ်ဆင်း။
ကြီး ရင် → ညာဆင်း။
တူ ရင် → ဒီ node ပြန်။

တန်ဖိုး ထပ်ကြည့်ဖို့ subtree တစ်ဝက်ကို ဖြတ်ပစ်လို့ $O(h)$ နဲ့ ရပါတယ်။

Time Complexity: $O(h)$ - tree အမြင့် (balance ဖြစ်ရင် $O(\log n)$ )။
Space Complexity: $O(1)$ - iterative (extra space မလို)။ recursive ဆိုရင် stack အတွက် $O(h)$ ။

Java Solution

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while (root != null && root.val != val) {
            root = (val < root.val) ? root.left : root.right;  // ငယ်→ဘယ်, ကြီး→ညာ
        }
        return root;   // တွေ့တဲ့ node (သို့) null
    }
}

၂။ Validate Binary Search Tree

Binary tree တစ်ခုရဲ့ root ပေးထားသည်။ အဲ့ tree က မှန်ကန်တဲ့ BST ဟုတ်မဟုတ် စစ်ပါ။

Example 1:

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

Output: false — 4 က 5 ၏ ညာဘက်မှာ ရှိပေမယ့် 5 ထက် ငယ်နေ၊ 3 ကလည်း 5 ထက် ငယ်ပေမယ့် ညာဘက်မှာ ရှိ

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

သတိ ထားရမယ့် ထောင်ချောက် — node တစ်ခုစီကို "left child < ကိုယ် < right child " လောက်သာ စစ်ရင် မလုံလောက်ပါ။ အပေါ်က ဥပမာမှာ 3 က သူ့မိဘ 4 ထက် ငယ်ပေမယ့်၊ tree တစ်ခုလုံး အနေနဲ့ 3 က root 5 ရဲ့ ညာဘက် subtree ထဲ ရှိနေတဲ့အတွက် 5 ထက် ကြီးရမယ် — ဒါ ချိုးဖောက်ထားပါတယ်။

မှန်ကန်တဲ့ နည်းက — node တစ်ခုစီအတွက် ခွင့်ပြု အပိုင်းအခြား (min, max) ကို လိုက်သယ်သွားတာ ဖြစ်ပါတယ် —

ဘယ်ဘက် ဆင်းတဲ့အခါ — အမြင့်ဆုံး (max) က လက်ရှိ node တန်ဖိုး ဖြစ်လာသည် (ဘယ်ဘက် အကုန် ဒီထက် ငယ်ရမယ်)။
ညာဘက် ဆင်းတဲ့အခါ — အနိမ့်ဆုံး (min) က လက်ရှိ node တန်ဖိုး ဖြစ်လာသည် (ညာဘက် အကုန် ဒီထက် ကြီးရမယ်)။
node တစ်ခုစီ သူ့ (min, max) အတွင်း ရှိမှ မှန်။

အခြားနည်း: BST ကို inorder ဖြတ်ရင် sorted ထွက်ရမယ် — ဒါကြောင့် inorder ဖတ်ရင်း "အရင် ဖတ်ထားတာထက် အမြဲ ကြီးနေလား" စစ်ရင်လည်း ရပါတယ်။ ဒီမှာ (min, max) range နည်းကို ပြထားပါတယ်။

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

Java Solution

class Solution {
    public boolean isValidBST(TreeNode root) {
        return validate(root, null, null);   // အစ — range ကန့်သတ်ချက် မရှိ
    }

    // node က (min, max) အတွင်း ရှိရမည် (null = ကန့်သတ်မရှိ)
    private boolean validate(TreeNode node, Integer min, Integer max) {
        if (node == null) return true;                       // base case
        if (min != null && node.val <= min) return false;    // အနိမ့် ဖောက်
        if (max != null && node.val >= max) return false;    // အမြင့် ဖောက်
        // ဘယ်ဆင်း — max ကို node.val အဖြစ် ကျုံ့၊  ညာဆင်း — min ကို node.val
        return validate(node.left, min, node.val)
            && validate(node.right, node.val, max);
    }
}

၃။ Kth Smallest Element in a BST

BST တစ်ခုရဲ့ root နဲ့ ကိန်း k ပေးထားသည်။ k ခုမြောက် အငယ်ဆုံး (kth smallest) တန်ဖိုးကို ပြန်ပါ (k က ၁ ကနေ စသည်)။

Example 1:

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

k = 1 → Output: 1 (inorder = [1,2,3,4] → ၁ ခုမြောက် အငယ်ဆုံး)

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

ဒါက BST ရဲ့ inorder = sorted ဂုဏ်သတ္တိ ကို တိုက်ရိုက် အသုံးချတာ ဖြစ်ပါတယ်။ BST ကို inorder ဖြတ်ရင် တန်ဖိုးတွေ ငယ်→ကြီး ထွက်လာလို့၊ inorder ရဲ့ k ခုမြောက် က kth smallest ဖြစ်ပါတယ်။

အရေးကြီးတာ — tree တစ်ခုလုံး inorder လုပ်စရာ မလို။ inorder ဖတ်ရင်း k ခုမြောက် ရောက်တာနဲ့ ရပ် လို့ ရပါတယ်။

inorder အစီအစဉ် (ဘယ် → ကိုယ် → ညာ) နဲ့ ဆင်း။
node တစ်ခု ဖတ်တိုင်း counter တိုး။ counter က k ရောက်ရင် အဲ့ node က အဖြေ။

Time Complexity: $O(h + k)$ - အငယ်ဆုံးဆီ ဆင်းဖို့ $O(h)$ + node k ခု ဖတ်။ အဆိုးဆုံး $O(n)$ ။
Space Complexity: $O(h)$ - recursion stack။

Java Solution

class Solution {
    private int count = 0;
    private int result = 0;

    public int kthSmallest(TreeNode root, int k) {
        inorder(root, k);
        return result;
    }

    // true ပြန်ရင် "k ခုမြောက် တွေ့ပြီ" → recursion အကုန် ရပ်
    private boolean inorder(TreeNode node, int k) {
        if (node == null) return false;
        if (inorder(node.left, k)) return true;   // ဘယ် (ပိုငယ်) အရင်
        count++;                                   // node တစ်ခု ဖတ်ပြီ
        if (count == k) {                          // k ခုမြောက် ရောက်ပြီ
            result = node.val;
            return true;                           // ➜ ဒီကနေ အပေါ်ကို ရပ်တန့်
        }
        return inorder(node.right, k);             // ညာ
    }
}

၄။ Lowest Common Ancestor of a BST

BST တစ်ခုနဲ့ node ၂ ခု (p, q) ပေးထားသည်။ သူတို့ ၂ ခုရဲ့ lowest common ancestor (LCA) ကို ပြန်ပါ။

Example 1:

graph TD
    N6((6)) --> N2((2))
    N6 --> N8((8))
    N2 --> N0((0))
    N2 --> N4((4))
    N8 --> N7((7))
    N8 --> N9((9))

p = 2, q = 8 → Output: 6 (2 က ဘယ်ဘက်, 8 က ညာဘက် — ၆ မှာ ကွဲ)

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

အခန်း ၁၃ မှာ သာမန် Binary Tree အတွက် LCA ကို subtree ၂ ဘက် ရှာပြီး $O(n)$ နဲ့ ဖြေခဲ့ပါတယ်။ BST မှာတော့ "ဘယ်ငယ်၊ ညာကြီး" rule ကြောင့် ပိုလွယ်လွယ် ( $O(h)$ ) ဖြေနိုင်ပါတယ်။

idea — node တစ်ခုမှာ ရပ်ပြီး p, q ၂ ခု ဘယ်ဘက်လား ညာဘက်လား ကြည့်ရုံပါ —

p, q ၂ ခုလုံး လက်ရှိ node ထက် ငယ် ရင် → LCA က ဘယ်ဘက်မှာ → ဘယ်ဆင်း။
၂ ခုလုံး ကြီး ရင် → ညာဘက်မှာ → ညာဆင်း။
ကွဲ သွားရင် (တစ်ခု ငယ်၊ တစ်ခု ကြီး၊ သို့ တစ်ခုက လက်ရှိ node နဲ့ တူ) → လက်ရှိ node ကိုယ်တိုင်က LCA။

ဆိုလိုတာ — p နဲ့ q ၂ ခု ပထမဆုံး ကွဲသွားတဲ့ နေရာ က LCA ဖြစ်ပါတယ်။

Time Complexity: $O(h)$ - တစ်ဘက်တည်း ဆင်း (balance ဖြစ်ရင် $O(\log n)$ )။
Space Complexity: $O(1)$ - iterative။

Java Solution

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            if (p.val < root.val && q.val < root.val) {
                root = root.left;        // ၂ ခုလုံး ငယ် → ဘယ်
            } else if (p.val > root.val && q.val > root.val) {
                root = root.right;       // ၂ ခုလုံး ကြီး → ညာ
            } else {
                return root;             // ကွဲ → ဒီ node က LCA
            }
        }
        return null;
    }
}

၅။ Insert into a Binary Search Tree

BST တစ်ခုရဲ့ root နဲ့ ကိန်း val ပေးထားသည်။ val ကို BST ထဲ ထည့်ပြီး (rule မပျက်စေဘဲ) update လုပ်ထားတဲ့ tree ရဲ့ root ကို ပြန်ပါ။ val က tree ထဲ မရှိဘူးလို့ အာမခံထားသည်။

Example 1:

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

val = 5 ထည့်ပြီးရင် (5 > 4 → ညာ, 5 < 7 → ဘယ်, နေရာလွတ်မှာ ချ):

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

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

ဒါက အပေါ်က Insert ကို တိုက်ရိုက် အသုံးချတာ ဖြစ်ပါတယ်။ search လုပ်သလိုပဲ "ဘယ်ငယ်၊ ညာကြီး" အလိုက် ဆင်းသွားပြီး — နေရာလွတ် (null) ရောက်တာနဲ့ အဲ့မှာ node အသစ် ချရုံပါ။ ဒါက rule ကို မပျက်စေဘဲ မှန်ကန်တဲ့ နေရာ အလိုအလျောက် ရှာပေးပါတယ်။

val က လက်ရှိ node ထက် ငယ် ရင် → ဘယ်ဘက် ဆက်ဆင်း။
ကြီး ရင် → ညာဘက် ဆက်ဆင်း။
null ရောက်ရင် → အဲ့မှာ node အသစ် ချ။

Time Complexity: $O(h)$ - နေရာလွတ် ရှာဖို့ tree အမြင့်အတိုင်း ဆင်း (balance ဖြစ်ရင် $O(\log n)$ )။
Space Complexity: $O(h)$ - recursion stack။ iterative ဆိုရင် $O(1)$ ။

Java Solution

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);  // နေရာလွတ် → ဒီမှာ ချ
        if (val < root.val) {
            root.left = insertIntoBST(root.left, val);    // ငယ် → ဘယ်
        } else {
            root.right = insertIntoBST(root.right, val);  // ကြီး → ညာ
        }
        return root;
    }
}