Daraxt masalalari: balandlik, diametr, yo'l yig'indisi, LCA va serialize

Qisqacha: Daraxt masalalarining ko'pi bitta naqsh bilan yechiladi: har tugun bolalaridan javob oladi, ulardan o'zinikini hisoblaydi va otasiga qaytaradi (postorder). Balandlik, diametr, muvozanatni tekshirish va eng yaqin umumiy ajdod (LCA) — shu naqsh. Ikkinchi naqsh — tepadan pastga: ma'lumot parametr orqali tushadi (yo'l yig'indisi). Ikkalasi ham har tugunga bir marta keladi — O(n). Sodda yechim esa bir tugunni ko'p marta hisoblab, O(n²) ga tushib qoladi.

Bu darsda

• "Bolalardan javob olib, o'zinikini qaytaradi" naqshini taniysiz va unda balandlik, diametr va muvozanatni yozasiz.
• Sodda O(n²) yechimni bitta o'tishli O(n) yechimga aylantirasiz va farqni o'lchaysiz.
• Tepadan pastga naqsh bilan yo'l yig'indisini, ikki daraxtni birga yurish bilan simmetriyani tekshirasiz.
• Ikki tugunning eng yaqin umumiy ajdodini topasiz va daraxtni satrga yozib, qayta tiklaysiz.

Oldin bilishingiz kerak: Binary Search Tree, Daraxt bo'ylab yurish: DFS va BFS, Rekursiv fikrlash.

1. Nega bu kerak?

O'tgan darslarda daraxtni qurdik, aylandik, qidiruv daraxtini yasadik va muvozanatda ushladik. Endi shu bilimlar bilan amaliy savollarga javob beramiz.

«Bahor» kengaydi. Markaziy oshxonadan ikki filialga — Chilonzor va Yunusobodga — taom boradi, filiallardan esa yetkazish punktlariga. Bu tarmoq daraxt: ildiz — oshxona, barglar — punktlar. Jasur aka Sardorga bir nechta savol berdi:

1. Tarmoq necha qavatli? (balandlik)
2. Eng uzoq ikki punkt orasida nechta bosqich bor? (diametr)
3. Qaysi yo'nalishlarda yetkazish vaqti aniq 27 daqiqa? (yo'l yig'indisi)
4. Ikki punktga taomni qaysi eng yaqin umumiy filialdan jo'natish kerak? (eng yaqin umumiy ajdod)
5. Tarmoq sxemasini faylga qanday saqlab, keyin qayta ochish mumkin? (serialize)

Savollar har xil, lekin javoblarning tuzilishi o'xshash. Rekursiv fikrlash darsida "katta masalani kichik nusxalariga bo'lish" ni o'rgandik. Daraxtda kichik nusxa tayyor — har tugunning chap va o'ng shoxi. Bugun shu g'oyani ikki naqshga aylantiramiz.

2. Naqsh: bolalardan javob olish

2.1 Balandlik

Daraxt necha qavatli? Bu darsda balandlikni qavatlar soni bilan sanaymiz: bo'sh daraxt — 0, bitta tugun — 1. Daraxt atamalari darsidagi qirralar balandligidan u doim bittaga ko'p. Nega shunday? Diametr formulasi sodda chiqadi — buni pastda ko'rasiz.

Rekursiv o'ylaymiz: bo'sh daraxt — 0 qavat. Aks holda — chap va o'ng shoxdan kattasining balandligi, ustiga ildizning o'zi (+1):

const node = (value, left = null, right = null) =>
  ({ value, left, right });
const root = node(50,
  node(30, node(20), node(40, null, node(45))),
  node(70));

function height(current) {
  if (current === null) return 0;
  const left = height(current.left); // bolalardan javob
  const right = height(current.right);
  return 1 + Math.max(left, right); // o'zinikini qaytaradi
}

console.log(height(root)); // 4
console.log(height(null)); // 0

Qavatlar: 50 → 30 → 40 → 45 — to'rtta. Kodning shakliga qarang. Uch qadam bor:

1. Asos: bo'sh daraxt uchun javob (0).
2. Bolalardan so'rash: chap va o'ng shox uchun xuddi shu funksiya.
3. Birlashtirish: ikki javobdan o'zinikini yasash va qaytarish.

Bu — postorder (Daraxt bo'ylab yurish): tugun bolalaridan keyin ishlaydi. Funksiya javobga ishonadi: "chap shoxning balandligini rekursiya to'g'ri hisoblaydi" deb, faqat o'z qavatini qo'shadi. Har tugunga bir marta kelinadi — O(n) vaqt, O(h) stek.

Tekshirib ko'ring: Shu naqsh bilan tugunlar sonini qanday sanaysiz? Faqat birlashtirish qatorini yozing.

2.2 Bitta javob yetmasa — muvozanat

Daraxt muvozanatlimi (har tugunda balandlik farqi ≤ 1, AVL qoidasi)? Sodda yo'l: har tugunda chap va o'ng shox uchun height ni chaqirib, natijalarni solishtirish. Lekin height o'zi butun shoxni aylanadi — va buni har tugunda qilsak, pastki tugunlar qayta-qayta sanaladi.

To'g'ri yo'l — bitta o'tishda ikki javob: balandlik va "muvozanatlimi". Hiyla: muvozanat buzilsa, balandlik o'rniga maxsus qiymat qaytaramiz — -1. Haqiqiy balandlik hech qachon manfiy bo'lmaydi, shuning uchun -1 "pastda buzilgan" belgisi bo'ladi va yuqoriga uzatiladi. Kodini mashqlarda yozasiz.

3. Diametr: sodda va tez yechim

3.1 Masala

Diametr — daraxtdagi ikki tugun orasidagi eng uzun yo'l uzunligi (qirralar soni). Tarmoqda — eng uzoq ikki punkt orasidagi bosqichlar. Yo'l qandaydir tugunda "egiladi": chap shoxdan ko'tarilib, o'sha tugun orqali o'ng shoxga tushadi. Shu tugun orqali eng uzun yo'l = chap shox balandligi + o'ng shox balandligi.

Demak, javob — barcha tugunlar uchun shu yig'indilarning eng kattasi. Diqqat: eng uzun yo'l ildizdan o'tishi shart emas.

3.2 Sodda yechim

To'g'ridan-to'g'ri ta'rif bo'yicha yozamiz:

const node = (value, left = null, right = null) =>
  ({ value, left, right });
const height = (t) =>
  t === null ? 0 : 1 + Math.max(height(t.left), height(t.right));

function diameterSlow(t) {
  if (t === null) return 0;
  const through = height(t.left) + height(t.right); // shu tugundan
  const below = Math.max(diameterSlow(t.left), diameterSlow(t.right));
  return Math.max(through, below);
}

const root = node(50, node(30, node(20), node(40)), node(70));
console.log(diameterSlow(root)); // 3

To'g'ri ishlaydi, lekin har tugunda height butun pastki shoxni qaytadan aylanadi. Muvozanatli daraxtda bu O(n log n). Zanjirda esa birinchi tugun n ta, ikkinchisi n − 1 ta, uchinchisi n − 2 ta tugunni ko'radi. Jami taxminan n² ÷ 2, ya'ni O(n²).

3.3 G'oya: balandlikni qaytarib, rekordni yo'l-yo'lakay yangilash

height allaqachon har tugunda chap va o'ng balandlikni hisoblaydi! Ular aynan diametr uchun kerak. Demak, height ichida bitta qator qo'shamiz: left + right ni tashqi o'zgaruvchidagi rekord bilan solishtiramiz. Funksiya otaga hamon balandlikni qaytaradi, diametr esa yon tomonda yig'iladi.

Qavatlar bilan sanaganimiz shu yerda qo'l keladi. Tugunning chap shoxida 3 qavat bo'lsa, tugundan chap tomondagi eng chuqur bargigacha aynan 3 ta qirra bor. O'ng tomon uchun ham shunday. Demak, shu tugun orqali o'tadigan eng uzun yo'l = chap qavatlar + o'ng qavatlar, hech qanday "+1" yoki "−1" siz.

Kuzating. Tugun yonidagi h — u otasiga qaytargan balandlik (qavatlar). Qizil — yangi rekord qo'yilgan tugun:

Eng uzun yo'l 30 tugunida egildi: chapdan 3 qavat (20, 10, 5), o'ngdan 3 qavat (40, 45, 46). Ildiz orqali o'tadigan eng uzun yo'l — 4 + 1 = 5, bu kamroq. Agar faqat ildizni tekshirganimizda, xato javob olardik.

best — tashqi funksiyaning o'zgaruvchisi. Ichki height uni closure orqali ko'radi va yangilaydi. Shu tufayli funksiyaga ikkinchi qiymat qaytarish kerak bo'lmadi.

3.4 O'lchov

Ikkala yechimni eng yomon holatda — zanjirda o'lchadik:

Sodda yechim: n ikki baravar — vaqt to'rt baravar (×3,9–4,8), O(n²). Bitta o'tish: ikki baravar (×2,0), O(n). 4 000 tugunda farq 1 300 baravar. Kichik n da bitta o'tishli yechimning vaqti shovqinda yo'qoladi — 500 va 1 000 dagi raqamlar mikrosoniyalar.

Maslahat: "Har tugunda yordamchi funksiyani chaqiryapman, u ham butun shoxni aylanadi" — bu O(n²) belgisi. Odatda yordamchi funksiyaning natijasini qaytariladigan qiymatga qo'shish yoki tashqi o'zgaruvchiga yozish bilan bitta o'tishga aylantiriladi.

4. Ikkinchi naqsh: tepadan pastga

4.1 Yo'l yig'indisi

Har qirrada yetkazish vaqti bor (daqiqa). Oshxonadan qaysi punktgacha yo'l aynan 27 daqiqa? Bu yerda ma'lumot tepadan pastga oqadi: har tugun otasidan "qancha vaqt qoldi" degan sonni oladi va bolalariga kamaytirib uzatadi. Javob — barglarda: qolgan vaqt aynan 0 bo'lsa, yo'l topildi.

Qog'ozda 27 daqiqani izlaymiz. Oshxona (10) dan keyin 17 qoladi. Chilonzor (5) — 12 qoladi. Birinchi punkt 15 daqiqa — 12 dan ko'p, qoldiq manfiy: bu yo'l emas. Ikkinchi punkt 12 daqiqa — qoldiq aynan 0: topildi, 10 + 5 + 12 = 27. Yunusobod tomonida (8, keyin 7 yoki 20) 0 chiqmaydi.

const node = (value, left = null, right = null) =>
  ({ value, left, right });
// yetkazish vaqtlari (daqiqa): oshxona → filial → punkt
const routes = node(10,
  node(5, node(15), node(12)),
  node(8, node(7), node(20)));

function pathsWithSum(current, target, path = [], found = []) {
  if (current === null) return found;
  path.push(current.value); // tepadan pastga: yo'lni olib tushamiz
  const rest = target - current.value;
  if (current.left === null && current.right === null && rest === 0) {
    found.push([...path]); // bargga yetdik va summa to'g'ri
  }
  pathsWithSum(current.left, rest, path, found);
  pathsWithSum(current.right, rest, path, found);
  path.pop(); // qaytishda yo'ldan olib tashlaymiz
  return found;
}

console.log(pathsWithSum(routes, 27)); // [ [ 10, 5, 12 ] ]
console.log(pathsWithSum(routes, 100)); // []

Ikkita muhim detal bor. Birinchisi — barg sharti: yo'l punktda tugashi kerak, filialda emas. Ikkinchisi — path.pop(): bitta path massivi hamma chaqiruvlar uchun umumiy. Tugundan qaytishda uni olib tashlamasak, qo'shni shoxning yo'liga aralashib ketadi. Natijaga esa nusxa ([...path]) qo'yamiz — aks holda keyingi o'zgarishlar uni ham buzadi. Bu "qo'y — tekshir — olib tashla" usulini Backtracking asoslari darsida ko'rgan edik.

4.2 Qaysi naqsh qachon

Oddiy savol yordam beradi: "tugunga javob uchun nima kerak — bolalari haqidagi ma'lumotmi yoki ajdodlari haqidagimi?" Bolalari — pastdan tepaga. Ajdodlari — tepadan pastga.

Tekshirib ko'ring: Har tugunga "ildizdan shu yergacha jami vaqt" ni yozish kerak. Qaysi naqsh?

5. Eng yaqin umumiy ajdod (LCA)

5.1 Masala

LCA (Lowest Common Ancestor — eng yaqin umumiy ajdod) — ikki tugunning ikkalasini ham o'z shoxida saqlaydigan eng chuqur tugun. Tarmoqda — ikki punktga taom jo'natish mumkin bo'lgan eng yaqin filial. Tugun o'zining ajdodi ham hisoblanadi: Chilonzor va uning punkti Qatortol uchun LCA — Chilonzorning o'zi.

5.2 Bitta o'tishli yechim

Yana pastdan tepaga naqsh. Har tugun bolalaridan so'raydi: "sizning shoxingizda a yoki b bormi?" Javob — topilgan tugun yoki null:

• Tugunning o'zi a yoki b bo'lsa — o'zini qaytaradi.
• Ikkala bola ham nimadir topgan bo'lsa — a bir tomonda, b boshqa tomonda. Demak, shu tugun — LCA.
• Faqat bittasi topgan bo'lsa — o'sha javobni yuqoriga uzatadi.

Qog'ozda Qatortol va Novza uchun. Oshxona Chilonzordan so'raydi. Chilonzorning chapida Qatortol topildi, o'ngida Novza topildi — ikki tomonda. Demak, Chilonzor — LCA, u o'zini qaytaradi. Yunusobod shoxida ikkalasi ham yo'q — null. Oshxona bir tomondan Chilonzorni, ikkinchisidan null ni oldi va Chilonzorni yuqoriga uzatadi.

const node = (value, left = null, right = null) =>
  ({ value, left, right });
const root = node("Oshxona",
  node("Chilonzor", node("Qatortol"), node("Novza")),
  node("Yunusobod", node("Minor"), node("Bodomzor")));

function lowestCommon(current, a, b) {
  if (current === null) return null;
  if (current.value === a || current.value === b) return current;
  const left = lowestCommon(current.left, a, b);
  const right = lowestCommon(current.right, a, b);
  if (left !== null && right !== null) return current; // ikki tomonda
  return left ?? right; // topilgani yuqoriga uzatiladi
}

console.log(lowestCommon(root, "Qatortol", "Novza").value);
console.log(lowestCommon(root, "Novza", "Bodomzor").value);
console.log(lowestCommon(root, "Chilonzor", "Qatortol").value);

Konsolda:

Chilonzor
Oshxona
Chilonzor

Uchinchi holatga qarang: Chilonzor o'zini topib, darhol qaytdi va pastga (Qatortolga) tushmadi ham. Bu to'g'ri: Qatortol baribir uning shoxida. Funksiya ikkala tugun ham daraxtda borligiga tayanadi. Biri yo'q bo'lsa, u boshqasini qaytaradi — bunday holatda avval ikkalasining borligini tekshiring. Vaqt O(n).

5.3 BST'da osonroq

Agar daraxt BST bo'lsa, qiymatlarning o'zi yo'l ko'rsatadi. a va b ikkalasi joriy tugundan kichik — LCA chap shoxda. Ikkalasi katta — o'ngda. Aks holda ular tugunning ikki tomonida (yoki biri tugunning o'zi) — demak, LCA shu tugun. Bu bitta yo'l bo'ylab tushish: O(h), rekursiyasiz ham yoziladi:

const node = (value, left = null, right = null) =>
  ({ value, left, right });
const root = node(50,
  node(30, node(20), node(40)),
  node(70, node(60), node(80)));

function lcaBST(current, a, b) {
  while (current !== null) {
    if (a < current.value && b < current.value) {
      current = current.left;
    } else if (a > current.value && b > current.value) {
      current = current.right;
    } else {
      return current; // ajraldi — shu tugun
    }
  }
  return null;
}

console.log(lcaBST(root, 20, 40).value); // 30
console.log(lcaBST(root, 20, 80).value); // 50
console.log(lcaBST(root, 60, 70).value); // 70

Uchinchi qatorga qarang: 60 va 70 uchun javob — 70, chunki 60 uning shoxida. "Ajraldi" sharti a yoki b tugunning o'ziga teng bo'lgan holatni ham qamraydi.

Endi o'zingiz to'ldiring. Darsdagi 50 ildizli BST'da (chapida 30, uning bolalari 20 va 40; o'ngida 70) 20 va 40 uchun LCA — .

6. Ikki daraxtni birga yurish: simmetriya

Ba'zan bitta emas, ikkita tugunni birga aylanish kerak. Daraxt ko'zgudagi aksiga tengmi — ya'ni simmetrikmi? Chap shox o'ng shoxning ko'zgudagi aksi bo'lishi kerak. Ikki shox a va b aks bo'ladi, agar qiymatlari teng bo'lsa, a ning chapi b ning o'ngi bilan, a ning o'ngi b ning chapi bilan aks bo'lsa:

const node = (value, left = null, right = null) =>
  ({ value, left, right });

function isMirror(a, b) {
  if (a === null || b === null) return a === b; // ikkalasi bo'shmi
  return (
    a.value === b.value &&
    isMirror(a.left, b.right) && // tashqi juft
    isMirror(a.right, b.left) // ichki juft
  );
}

const isSymmetric = (root) =>
  root === null || isMirror(root.left, root.right);

const tray = node(1,
  node(2, node(3), node(4)),
  node(2, node(4), node(3)));
const crooked = node(1,
  node(2, null, node(3)),
  node(2, null, node(3)));
console.log(isSymmetric(tray), isSymmetric(crooked)); // true false

Birinchi qator nozik: a === null || b === null bo'lsa, ikkalasi ham null bo'lgandagina true. Bittasi bo'sh, ikkinchisi yo'q — aks emas. Ikkinchi daraxtda qiymatlar bir xil (1, 2, 3), lekin 3 lar ikkalasida ham o'ngda — ko'zgu aksi emas.

Simmetriyaga yaqin yana bir klassik masala — daraxtni ko'zguda aylantirish: har tugunning chap va o'ng bolasini almashtirish. Bu ham pastdan tepaga naqsh. Avval ikkala shox aylantiriladi, keyin ular joy almashadi:

const node = (value, left = null, right = null) =>
  ({ value, left, right });

function mirror(current) {
  if (current === null) return null;
  const left = mirror(current.left); // avval bolalar aylanadi
  const right = mirror(current.right);
  current.left = right; // keyin o'rinlari almashadi
  current.right = left;
  return current;
}

const root = node(50, node(30, node(20)), node(70));
mirror(root);
console.log(root.left.value, root.right.value); // 70 30
console.log(root.right.right.value); // 20

Funksiya daraxtni joyida o'zgartiradi — yangi tugun yaratmaydi. BST'ni ko'zguda aylantirsangiz, inorder kamayish tartibida chiqadi: chapda endi kattalar turadi. Vaqt O(n), qo'shimcha xotira — faqat stek, O(h).

7. Serialize va deserialize

7.1 Daraxtni satrga yozish

Tarmoq sxemasini faylga yoki localStorage ga saqlash kerak. Daraxt — xotiradagi obyektlar va havolalar, faylga esa satr yoziladi. Daraxtni satrga aylantirish — serialize (ketma-ketlash), qaytarish — deserialize.

Preorder yetmaydi: 50 30 70 dan ikki xil daraxt chiqishi mumkin (30 — chap bolami yoki 70 ning bolasimi?). Shuning uchun bo'sh joylarni ham yozamiz — # belgisi bilan. Shunda satr daraxtni bir ma'noda tasvirlaydi.

Qog'ozda 50 ildizli kichik daraxt uchun (50 ning chapida 30, 30 ning o'ngida 40; 50 ning o'ngida 70). Preorder bo'yicha: 50; uning chapi — 30; 30 ning chapi bo'sh — #; 30 ning o'ngi — 40; 40 ning ikkala bolasi bo'sh — #, #; endi 50 ning o'ngi — 70 va uning ikki bo'sh bolasi. Natija: 50,30,#,40,#,#,70,#,#:

const node = (value, left = null, right = null) =>
  ({ value, left, right });
const root = node(50, node(30, null, node(40)), node(70));

function serialize(current) {
  const parts = [];
  (function walk(n) {
    if (n === null) {
      parts.push("#"); // bo'sh joy ham yoziladi!
      return;
    }
    parts.push(String(n.value)); // preorder: avval o'zi
    walk(n.left);
    walk(n.right);
  })(current);
  return parts.join(",");
}

function deserialize(text) {
  const parts = text.split(",");
  let i = 0;
  function build() {
    const part = parts[i++];
    if (part === "#") return null;
    const n = node(Number(part));
    n.left = build(); // xuddi shu tartibda o'qiymiz
    n.right = build();
    return n;
  }
  return build();
}

const text = serialize(root);
console.log(text); // 50,30,#,40,#,#,70,#,#
console.log(serialize(deserialize(text)) === text); // true
console.log(JSON.stringify(root).length, text.length); // 136 21

deserialize preorderni o'sha tartibda "qayta o'ynaydi". U i ko'rsatkichi bilan satr bo'laklarini birma-bir oladi. # — bo'sh joy, son — yangi tugun, keyin uning chapi va o'ngi. i — tashqi funksiya o'zgaruvchisi, hamma build chaqiruvlari uni birga suradi.

Funksiya ichida (function walk(n) { ... })(current) — darhol chaqiriladigan funksiya (IIFE). U nomli, shuning uchun o'zini rekursiv chaqira oladi.

7.2 Nega JSON.stringify emas?

JSON.stringify(root) ham ishlaydi va JSON.parse daraxtni qaytaradi. Lekin oxirgi qatorga qarang: JSON 136 belgi, bizning format — 21. JSON har tugunda "value", "left", "right" kalit nomlarini takrorlaydi. Million tugunli daraxtda bu megabaytlar. Bundan tashqari, JSON faqat daraxt shaklidagi obyektni yozadi. Agar tugunda otaga havola (parent) bo'lsa, sikl paydo bo'ladi va JSON.stringify xato beradi: TypeError: Converting circular structure to JSON.

8. Chegaraviy holatlar

• Bo'sh daraxt. Balandlik 0, diametr 0, serialize — "#", LCA — null. Har funksiyada asos holati shuni beradi.
• Bitta tugun. Diametr 0 (qirra yo'q), balandlik 1. Yo'l yig'indisida ildizning o'zi barg.
• Manfiy qiymatlar. Yo'l yig'indisida manfiy vaqt bo'lmaydi, lekin pul (qaytarishlar) bo'lishi mumkin. Shuning uchun "summa oshib ketdi — to'xtaymiz" degan qisqartirish xato: keyingi manfiy son uni kamaytirishi mumkin.
• Chuqur daraxt. Rekursiv yechimlar o'n ming atrofidagi chuqurlikda (bizda 10 000–13 800) yiqiladi (Daraxt bo'ylab yurish). Ishonchsiz ma'lumotda — iterativ variant yoki chuqurlik chegarasi.
• Serialize'da , yoki # bor qiymat. Bizning format faqat sonlar uchun. Matnli qiymatlar uchun ajratgichni ekranlash yoki JSON kerak.

9. Ko'p uchraydigan xatolar

9.1 Diametrni faqat ildizda hisoblash

height(root.left) + height(root.right) — eng uzun yo'l ildizdan o'tsa to'g'ri. Darsdagi daraxtda bu 5 ni berardi, haqiqiy javob 6. Tuzatish: har tugunda rekordni yangilang.

9.2 Yo'l yig'indisida bargni tekshirmaslik

rest === 0 bo'lishi bilan yo'l topildi deyish — filialda ham to'xtab qoladi. Tuzatish: current.left === null && current.right === null shartini qo'shing.

9.3 Umumiy massivni qaytishda tozalamaslik

path.pop() unutilsa, keyingi shoxlarning yo'llari oldingi tugunlar bilan to'lib boradi. Natijaga nusxa o'rniga path ning o'zini qo'yish ham xuddi shunday xato beradi — oxirida hammasi bir xil (bo'sh) massiv bo'lib qoladi. Tuzatish: path.pop() va found.push([...path]).

9.4 Har tugunda qayta hisoblash

isBalanced ichida height ni chaqirish — O(n²). Tuzatish: bitta o'tishda bir nechta javob (balandlik + belgi -1).

10. Mashqlar

1-mashq (oson): Naqshni tanlang

Har savol uchun naqshni ayting (pastdan tepaga yoki tepadan pastga) va birlashtirish qatorini yozing: (a) daraxtdagi barglar soni; (b) har tugunning chuqurligini yozish; (c) eng kichik qiymat.

2-mashq (o'rta): Eng qimmat yo'nalish

maxPathSum(root) funksiyasini yozing: ildizdan istalgan bargga bo'lgan yo'llar ichida eng katta yig'indini qaytarsin. Darsdagi routes uchun javob — 38 (10 + 8 + 20). Ishora: pastdan tepaga naqsh; bitta bolasi bor tugunda bo'sh tomonni hisobga olmang.

const node = (value, left = null, right = null) =>
  ({ value, left, right });
const routes = node(10,
  node(5, node(15), node(12)),
  node(8, node(7), node(20)));

function maxPathSum(current) {
  if (current.left === null && current.right === null) {
    return current.value; // barg — yo'l shu yerda tugaydi
  }
  let best = -Infinity;
  if (current.left) best = Math.max(best, maxPathSum(current.left));
  if (current.right) best = Math.max(best, maxPathSum(current.right));
  return current.value + best;
}

console.log(maxPathSum(routes)); // 38
console.log(maxPathSum(node(-3, null, node(-2)))); // -5

3-mashq (qiyin): Muvozanat va serialize testlari

kurs/mashqlar/14/40-masalalar/masalalar.test.mjs faylida yozing:

1. isBalanced(root) — bitta o'tishda. Ishora: yordamchi checkedHeight buzilganda -1 qaytaradi va uni yuqoriga uzatadi.
2. Darsdagi serialize va deserialize.

Testlar (node:test): bo'sh va bitta tugun; ildizda teng, lekin pastda buzilgan daraxt; manfiy va nolli qiymatlar bilan aylanma (deepEqual); 5 000 qavatli zanjir.

// kurs/mashqlar/14/40-masalalar/masalalar.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

const node = (value, left = null, right = null) =>
  ({ value, left, right });

// -1 — "pastda allaqachon muvozanat buzilgan" belgisi
function checkedHeight(current) {
  if (current === null) return 0;
  const left = checkedHeight(current.left);
  if (left === -1) return -1;
  const right = checkedHeight(current.right);
  if (right === -1) return -1;
  if (Math.abs(left - right) > 1) return -1;
  return 1 + Math.max(left, right);
}
const isBalanced = (root) => checkedHeight(root) !== -1;

function serialize(root) {
  const parts = [];
  (function walk(n) {
    if (n === null) {
      parts.push("#");
      return;
    }
    parts.push(String(n.value));
    walk(n.left);
    walk(n.right);
  })(root);
  return parts.join(",");
}

function deserialize(text) {
  const parts = text.split(",");
  let i = 0;
  function build() {
    const part = parts[i++];
    if (part === "#") return null;
    const n = node(Number(part));
    n.left = build();
    n.right = build();
    return n;
  }
  return build();
}

test("bo'sh va bitta tugun", () => {
  assert.equal(isBalanced(null), true);
  assert.equal(isBalanced(node(1)), true);
  assert.equal(serialize(null), "#");
  assert.equal(deserialize("#"), null);
});

test("muvozanat: farq 1 — ha, zanjir — yo'q", () => {
  assert.equal(isBalanced(node(2, node(1), null)), true);
  assert.equal(isBalanced(node(3, node(2, node(1)), null)), false);
  // ildizda teng, lekin pastda buzilgan
  const deep = node(5,
    node(3, node(2, node(1)), null),
    node(8, null, node(9, null, node(10))));
  assert.equal(isBalanced(deep), false);
});

test("serialize → deserialize — aynan o'sha daraxt", () => {
  const tree = node(-5, node(0, null, node(7)), node(12));
  const text = serialize(tree);
  assert.equal(text, "-5,0,#,7,#,#,12,#,#");
  assert.deepEqual(deserialize(text), tree);
});

test("5 000 qavatli zanjir ham qaytadi", () => {
  let chain = null;
  for (let i = 5000; i >= 1; i--) chain = node(i, null, chain);
  const back = deserialize(serialize(chain));
  assert.equal(serialize(back), serialize(chain));
  assert.equal(isBalanced(back), false);
});

✔ bo'sh va bitta tugun (0.7935ms)
✔ muvozanat: farq 1 — ha, zanjir — yo'q (0.1697ms)
✔ serialize → deserialize — aynan o'sha daraxt (0.706ms)
✔ 5 000 qavatli zanjir ham qaytadi (12.1191ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 92.7829

4-mashq: Amaliy tajriba — naqshlar jadvali

kurs/mashqlar/14/MURAKKABLIK.md ga bugungi masalalarni qo'shing va har biriga naqsh ustunini yozing.

| Masala | Yechim | Vaqt | Xotira |
|---|---|---|---|
| Balandlik | pastdan tepaga | O(n) | O(h) |
| Diametr | har tugunda height (sodda) | O(n²) | O(h) |
| Diametr | bitta o'tish, rekord | O(n) | O(h) |
| Muvozanat | -1 belgisi bilan | O(n) | O(h) |
| Yo'l yig'indisi | tepadan pastga + pop | O(n·h) nusxalar bilan | O(h) |
| LCA | pastdan tepaga | O(n); BST'da O(h) | O(h) |
| Serialize | preorder + # | O(n) | O(n) |

git add 14/MURAKKABLIK.md 14/40-masalalar
git commit -m "14/40: daraxt masalalari — muvozanat va serialize"

11. Real ishda

• Fayl va papkalar. Papka hajmi, eng chuqur papka, "bu fayllarning umumiy papkasi" (LCA) — Git ham ikki commit'ning umumiy ajdodini (git merge-base) topadi. U yerda daraxt emas, graf, lekin g'oya o'xshash.
• UI daraxtlari. DOM'da ikki elementning umumiy ota elementi — hodisa qayerda tutilishini aniqlashda kerak. Komponentlar daraxtini satrga yozish va qaytarish — server tomonida render qilishning asosi (bu mavzular 17-qismdan, hozir bilish shart emas).
• Saqlash va tarmoq. Daraxtni faylga, localStorage ga yoki tarmoq orqali yuborish — har doim serialize. Kompakt format megabaytlarni tejaydi.
• Intervyu. Diametr, LCA, yo'l yig'indisi, simmetriya, serialize — LeetCode'dagi eng mashhur daraxt masalalari (543, 236, 112/113, 101, 297). Har birida intervyuchi O(n²) ni O(n) ga tushirishni kutadi.

Xulosa

• Pastdan tepaga naqsh: asos → bolalardan so'rash → birlashtirib qaytarish. Balandlik, diametr, muvozanat, LCA — hammasi shu.
• Tepadan pastga naqsh: ma'lumot parametr bilan tushadi (yo'l yig'indisi, chuqurlik); umumiy massivni qaytishda tozalang.
• Har tugunda yordamchi funksiyani chaqirish — O(n²); natijani qaytarish yoki rekordni yo'l-yo'lakay yangilash — O(n). Diametrda farq 4 000 tugunda 1 300 baravar.
• Diametr ildizdan o'tishi shart emas; LCA tugunning o'zi ham bo'lishi mumkin.
• Serialize — preorder va bo'sh joylar uchun #; JSON dan ancha ixcham.

Keyingi dars: Trie (prefiks daraxti) — so'zlarni harfma-harf saqlaydigan daraxt va menyu qidiruvidagi avtoto'ldirish; vazifalar ilovasidagi teg takliflari.

Manbalar

• LeetCode: 543 "Diameter of Binary Tree", 236 "Lowest Common Ancestor of a Binary Tree", 113 "Path Sum II" — leetcode.com.
• LeetCode: 101 "Symmetric Tree", 226 "Invert Binary Tree", 297 "Serialize and Deserialize Binary Tree" — shartlari boshqacha, g'oyasi shu darsdagi.
• Steven Skiena, "The Algorithm Design Manual", 3-nashr, Springer, 2020 — 3-bob (daraxtlar va binary search trees).
• MDN: JSON.stringify() — "TypeError: cyclic object value" / "Converting circular structure to JSON" — developer.mozilla.org