Daraxt bo'ylab yurish: DFS va BFS — preorder, inorder, postorder va level order

Qisqacha: Daraxtning hamma tugunini ko'rib chiqishning ikki yo'li bor. DFS (chuqurlik bo'yicha) bitta shoxni oxirigacha tushib, keyin qaytadi — rekursiya yoki stek bilan. Tugunni qachon yozishga qarab uch tartib chiqadi: preorder (o'zi, chap, o'ng), inorder (chap, o'zi, o'ng), postorder (chap, o'ng, o'zi). BFS (kenglik bo'yicha) daraxtni qavatma-qavat o'qiydi — navbat bilan. Hammasi O(n) vaqt; xotira DFS da balandlikka, BFS da eng keng qavatga bog'liq.

Bu darsda

• Rekursiv yurishda har tugunga uch marta kelishni ko'rasiz va undan preorder, inorder, postorder tartiblarini chiqara olasiz.
• Rekursiyani o'z stekingiz bilan almashtirib, chuqur daraxtda Maximum call stack size exceeded dan qutulasiz.
• Daraxtni navbat bilan qavatma-qavat (level order) aylana olasiz va shift tuzog'ini o'lchov bilan tushuntirasiz.
• Har yurishning vaqt va xotira murakkabligini ayta olasiz.

Oldin bilishingiz kerak: Daraxt atamalari va binar daraxt, Stack (LIFO), Queue va deque (FIFO), Rekursiya asoslari.

1. Nega bu kerak?

O'tgan darsda daraxt nima ekanini ko'rdik: ildiz, tugunlar, barglar, ota va bolalar. Endi daraxt bilan ishlash kerak. «Bahor» saytida menyu ham daraxt: ildizda "Menyu", uning bolalari — "Taomlar" va "Ichimliklar", ularning ichida — taomlar.

Jasur aka Sardorga uchta vazifa berdi:

1. Menyuni saytga chiqarish: har bo'lim, uning ostida — ichidagilari, surilgan holda.
2. Har bo'limda nechta taom borligini hisoblash.
3. Mobil ilova uchun menyuni qavatma-qavat berish: avval bo'limlar, keyin taomlar.

Uchala vazifada ham daraxtning hamma tugunini bir martadan ko'rish kerak. Massivda bu oson: for sikli 0 dan oxirigacha yuradi. Daraxtda esa "keyingi element" degan narsa yo'q — har tugunning bir nechta bolasi bor. Qaysi tartibda yuramiz? Bugun shunga javob beramiz.

Bu «Bahor» omborini sanab chiqishga o'xshaydi. Omborda ikkita shkaf, har shkafda javonlar, har javonda qutilar bor. Sardor ikki xil sanashi mumkin. Birinchi yo'l: birinchi shkafni ochib, uning har javonini, har qutisini oxirigacha ko'radi, keyin ikkinchi shkafga o'tadi. Ikkinchi yo'l: avval ikkala shkafga bir qaraydi, keyin hamma javonlarga, eng oxirida hamma qutilarga. Daraxtda ham shunday ikki yo'l bor.

2. Ikki yo'l: chuqurlikka va kenglikka

DFS (Depth-First Search — chuqurlik bo'yicha aylanish) — bitta shoxdan iloji boricha pastga tushadi, barga yetgach qaytib, keyingi shoxga o'tadi. Ombor misolida — bitta shkafni oxirigacha ko'rib, keyin keyingisiga o'tish.

BFS (Breadth-First Search — kenglik bo'yicha aylanish) — avval ildizni, keyin uning hamma bolalarini, keyin nevaralarini ko'radi. Qavatma-qavat — ombordagi ikkinchi yo'l: shkaflar, keyin javonlar, keyin qutilar. Inglizcha manbalarda daraxt uchun BFS ko'pincha level order (daraja tartibi) deb ataladi.

Darsdagi asosiy misol — 7 tugunli binar daraxt. Unda «Bahor» buyurtma raqamlari turibdi:

          50
        /    \
      30      70
     /  \    /  \
   20   40  60   80

Kodda har tugun — uchta maydonli obyekt: qiymat (value), chap bola (left) va o'ng bola (right). Bola yo'q bo'lsa — null. Tugunni qisqa yaratish uchun yordamchi funksiya yozamiz:

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)));

console.log(root.left.right.value); // 40
console.log(root.right.left.value); // 60
console.log(root.right.left.left); // null

root.left.right — "ildizdan chapga, keyin o'ngga" degani: 50 → 30 → 40. Bu o'tgan darsdagi node yordamchisining o'zi. Arrow funksiya obyekt qaytarganda uni qavsga olamiz — ({ ... }), aks holda jingalak qavs funksiya tanasi deb o'qiladi (Arrow funksiyalar).

3. DFS rekursiya bilan: uch tashrif

3.1 Har tugunga uch marta kelamiz

Daraxt rekursiv tuzilma: har tugunning chap va o'ng bolasi — o'zi ham kichik daraxt. Shuning uchun yurish ham rekursiv: "tugunni ko'r, chap daraxtni yur, o'ng daraxtni yur". To'xtash sharti — null: bo'sh daraxtda yuradigan joy yo'q.

Bu funksiya har tugunga uch marta keladi. Birinchi marta — tushib kelganda. Ikkinchi marta — chap shoxdan qaytganda. Uchinchi marta — o'ng shoxdan qaytganda. Har tashrifda qiymatni alohida ro'yxatga yozamiz va kuzatamiz.

Boshini so'z bilan yurib chiqamiz. 50 ga tushib keldik — birinchi tashrif, 50 ni pre ga yozamiz. Chapga, 30 ga tushamiz — pre ga 30. Yana chapga, 20 ga — pre ga 20. 20 ning chapi null — darhol qaytamiz: bu 20 ga ikkinchi tashrif, uni ino ga yozamiz. O'ngi ham null — uchinchi tashrif, 20 post ga tushadi. Endi 30 ga qaytdik (chapdan) — 30 ino ga. Qolganini vizualda kuzating. Sariq tugunlar — hali tugamagan, stekda kutayotgan chaqiruvlar:

Uch ro'yxat — uch xil tartib:

Nomlarni eslab qolish oson: "pre" — oldin, "in" — o'rtada, "post" — keyin. Gap tugunning o'zi bolalaridan oldin, o'rtasida yoki keyin yozilishida.

3.2 Uchala tartib nimaga kerak

• Preorder — ota bolalaridan oldin keladi. Daraxtni nusxalash, saqlash yoki chop etish shu tartibda qilinadi: avval bo'lim nomi, keyin ichidagilar.
• Inorder — natijaga qarang: 20, 30, 40, … — o'sish tartibida! Tasodif emas: bu daraxtda har tugunning chapida kichik, o'ngida katta qiymatlar turibdi. Bunday daraxt — binary search tree, uni keyingi darsda o'rganamiz.
• Postorder — ota bolalaridan keyin keladi. Bolalardan ma'lumot yig'ib, otada hisoblash kerak bo'lsa — shu tartib: papka hajmi, bo'limdagi taomlar soni, daraxtni o'chirish (avval bolalar, keyin ota).

Tekshirib ko'ring: Bu daraxtda preorder qanday chiqadi?

text

     8
    / \
   3   10
      /
     9

Endi o'zingiz to'ldiring. Shu daraxtda postorder bo'yicha oxirgi yoziladigan tugun — [:8]. Postorderda birinchi yoziladigan tugun esa — [:3].

3.3 Ko'p bolali daraxt: «Bahor» menyusi

Menyu binar daraxt emas: "Taomlar" bo'limida uchta bola bor. Bunday daraxtda tugun bolalarni massivda saqlaydi — children. Bu o'tgan darsdagi menyuning aynan o'zi. Yurish o'zgarmaydi, faqat ikkita rekursiv chaqiruv o'rniga sikl. Jasur akaning birinchi va ikkinchi vazifasi:

const menu = {
  name: "Menyu",
  children: [
    { name: "Taomlar", children: [
      { name: "osh", children: [] },
      { name: "lag'mon", children: [] },
      { name: "manti", children: [] },
    ] },
    { name: "Ichimliklar", children: [
      { name: "ko'k choy", children: [] },
      { name: "Sharbatlar", children: [
        { name: "olma", children: [] },
      ] },
    ] },
  ],
};

// preorder: avval o'zi, keyin bolalari
function printMenu(item, depth = 0) {
  console.log("  ".repeat(depth) + item.name);
  for (const child of item.children) printMenu(child, depth + 1);
}

// postorder: avval bolalari, keyin o'zi
function countDishes(item) {
  if (item.children.length === 0) return 1; // barg — bitta taom
  let total = 0;
  for (const child of item.children) total += countDishes(child);
  console.log(`${item.name}: ${total} ta`);
  return total;
}

printMenu(menu);
countDishes(menu);

Konsolda:

Menyu
  Taomlar
    osh
    lag'mon
    manti
  Ichimliklar
    ko'k choy
    Sharbatlar
      olma
Taomlar: 3 ta
Sharbatlar: 1 ta
Ichimliklar: 2 ta
Menyu: 5 ta

Birinchi funksiya bo'lim nomini ichidagilaridan oldin chiqaradi — preorder. Parametr depth — chuqurlik: har pastga tushishda bittaga oshadi va shuncha marta ikki bo'sh joy qo'yiladi. Ikkinchi funksiya esa "Menyu: 5 ta" ni oxirida chiqardi: menyuning jami uchun avval ikkala bo'lim hisoblanishi kerak edi — postorder. "Sharbatlar: 1 ta" ham "Ichimliklar" dan oldin chiqdi: ichki bo'lim tashqisidan oldin hisoblanadi.

Ko'p bolali daraxtda inorder yo'q: "chap va o'ng o'rtasi" degan joy aniq emas. Preorder va postorder esa istalgan daraxtda ishlaydi.

Maslahat: Brauzerdagi DOM ham ko'p bolali daraxt. document.querySelectorAll("li") elementlarni hujjat tartibida qaytaradi — bu aynan preorder DFS: avval ota element, keyin uning bolalari, chapdan o'ngga.

4. DFS stek bilan: rekursiyasiz

4.1 Chuqur daraxt stekni to'ldiradi

Rekursiv yurish chiroyli, lekin har kutayotgan chaqiruv chaqiruvlar stekida joy oladi (Xotira murakkabligi darsini eslang). Muvozanatli daraxtda chuqurlik kichik: million tugunda ham 20 atrofida. Lekin daraxt "ro'yxatga o'xshab" bir tomonga cho'zilsa — chuqurlik n ga teng. Bunday daraxt, masalan, buyurtmalar o'sish tartibida kelganda paydo bo'ladi. Buni Balanslangan daraxtlar darsida ko'ramiz. Mana misol:

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

function sumTree(node) {
  if (node === null) return 0;
  return node.value + sumTree(node.left) + sumTree(node.right);
}

let chain = null; // har tugunning faqat o'ng bolasi bor
for (let i = 1; i <= 100000; i++) chain = node(1, null, chain);
console.log(sumTree(chain));

Konsolda:

RangeError: Maximum call stack size exceeded

Tarjimasi: "Chaqiruvlar stekining eng katta o'lchamidan oshib ketildi." Kodda xato yo'q — to'xtash sharti ham bor. Muammo faqat chuqurlikda. Bizning kompyuterda (Node 24) sumTree birinchi chaqiruvda taxminan 11 000 chuqurlikkacha ishladi. V8 funksiyani optimallashtirgandan keyin har chaqiruv stekda kamroq joy oladi va chegara 13 800 atrofiga ko'tariladi. O'tgan darsdagi height esa 10 000 da yiqilgan edi. Aniq raqam funksiyaga bog'liq, lekin tartibi bir xil — o'n minglar.

4.2 O'z stekimiz

Yechim — rekursiyani o'zimiz boshqaradigan stek bilan almashtirish. Rekursiyasiz, faqat sikl bilan yozilgan variant iterativ deyiladi. Stack — oddiy massiv: push bilan tepaga qo'yamiz, pop bilan tepadan olamiz. Massiv kompyuterning katta xotirasida (heap) yashaydi, chaqiruvlar stekida emas — shuning uchun million element ham sig'adi.

Preorder uchun qoida: tugunni stekdan olamiz va yozamiz, keyin bolalarini stekka qo'yamiz. Bir nozik joy bor: stek oxirgi qo'yilganni birinchi beradi. Chap bola birinchi chiqishi uchun uni oxirida qo'yamiz.

Qog'ozda: stekda [50]. 50 ni olib yozamiz, avval 70 ni, keyin 30 ni qo'yamiz — stek [70, 30]. Tepada 30: uni olib yozamiz, 40 va 20 ni qo'yamiz — [70, 40, 20]. Keyin 20 ni olamiz (bolasi yo'q), keyin 40 ni, keyin 70 ni. Natija: 50 30 20 40 70 … — rekursiv preorderning aynan o'zi:

Natija rekursiv preorder bilan aynan bir xil. Endi 100 000 chuqurlikdagi daraxt ham muammo emas:

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

function sumTreeLoop(root) {
  if (root === null) return 0;
  let total = 0;
  const stack = [root];
  while (stack.length > 0) {
    const current = stack.pop();
    total += current.value;
    if (current.right) stack.push(current.right);
    if (current.left) stack.push(current.left);
  }
  return total;
}

let chain = null;
for (let i = 1; i <= 100000; i++) chain = node(1, null, chain);
console.log(sumTreeLoop(chain)); // 100000
console.log(sumTreeLoop(null)); // 0

Ikkinchi qatorga qarang: bo'sh daraxt (null) uchun alohida tekshiruv bor. Usiz stack = [null] bo'lardi va current.value xato berardi.

4.3 Inorder va postorder stek bilan

Inorder stek bilan biroz murakkabroq: avval iloji boricha chapga tushamiz va yo'ldagi hamma tugunni stekka qo'yamiz. Chapda joy qolmagach — stekdan olib yozamiz va uning o'ng shoxiga o'tamiz. Bu kodni mashqlarda o'zingiz yozasiz.

Postorder uchun qulay hiyla bor. Preorder kodida bolalar tartibini almashtiring: avval chapni, keyin o'ngni stekka qo'ying. Natija "o'zi, o'ng, chap" tartibida chiqadi. Uni teskari aylantirsangiz — "chap, o'ng, o'zi", ya'ni postorder. Bitta qo'shimcha massiv evaziga.

Tekshirib ko'ring: Sardor preorder kodida ikki qatorni almashtirib yubordi: avval left, keyin right ni stekka qo'ydi. 7 tugunli daraxtimizda nima chiqadi?

5. BFS: qavatma-qavat

5.1 Sodda yechim: har qavat uchun qaytadan

Jasur akaning uchinchi vazifasi: menyuni qavatma-qavat berish. Birinchi xayolga keladigan yechim — DFS ni bilganimiz uchun undan foydalanish. 0-qavatni yig'ish uchun daraxtni aylanamiz va chuqurligi 0 bo'lgan tugunlarni olamiz. Keyin yana boshidan — chuqurligi 1 bo'lganlarni. Shunday qilib, eng chuqur qavatgacha boramiz.

Bu ishlaydi, lekin har qavat uchun daraxt qaytadan aylaniladi. Balandligi h bo'lgan daraxtda — h marta. Vaqt O(n · h). Muvozanatli daraxtda h ≈ log₂ n, bu hali chidasa bo'ladi. Cho'zilgan daraxtda esa h = n, va vaqt O(n²). O'lchadik — har tugunda bitta bola bor (eng yomon holat):

n ikki baravar — vaqt to'rt baravar. Bu kvadratik o'sish (Asosiy murakkablik sinflari). 100 000 tugunda bu daqiqalar bo'lardi.

5.2 G'oya: navbat

To'g'ri yechim — navbat (queue). Navbat oshxonadagi buyurtmalar kabi ishlaydi: birinchi kelgan birinchi xizmat qiladi. Qoida oddiy: navbat boshidan tugunni olamiz, yozamiz va uning bolalarini navbat oxiriga qo'yamiz. Bolalar ota qavatidagi hamma tugunlardan keyin turadi — shuning uchun qavatlar aralashmaydi.

Qog'ozda: navbatda [50]. 50 ni olib yozamiz, 30 va 70 ni oxiriga qo'yamiz — [30, 70]. 30 ni olamiz, 20 va 40 ni qo'yamiz — [70, 20, 40]. Ko'ryapsizmi, 20 va 40 70 ning orqasida turibdi: ikkinchi qavat tugamaguncha uchinchisiga navbat kelmaydi. Endi 70 ni olamiz, 60 va 80 ni qo'yamiz — [20, 40, 60, 80]. Qolganlari bolasiz.

Kuzating: sariq — navbatda kutayotganlar, yashil — allaqachon yozilganlar:

Har tugun navbatga bir marta kiradi va bir marta chiqadi. Vaqt — O(n), qavatlar soniga bog'liq emas.

5.3 shift tuzog'i

Kodda nega queue.shift() emas, head ko'rsatkichi? shift massivning boshidan oladi, lekin qolgan hamma elementni bir qadam chapga suradi. Bu O(n) amal — JS o'rnatilgan amallarining narxi darsida ko'rgan edik. head usulida esa hech narsa surilmaydi: faqat "navbat boshi qayerda" degan raqam oshadi. Ikkala variantni to'liq binar daraxtda o'lchadik:

20 000 dan 40 000 ga o'tganda shift varianti 550 baravar sekinlashdi! Sababi V8 dagi hiylada. Kichik massivda shift elementlarni surmaydi — massiv boshini bir katakka "kesib" qo'yadi, bu tez. Chegarani Queue va deque darsida ko'rgan edik: massiv zaxirasi 16 384 katakka yetganda (push bilan taxminan 15 000–16 000 elementda) bu hiyla ishlamay qoladi. To'liq binar daraxtda navbat eng keng qavatni ushlaydi — tugunlarning yarmini. 20 000 tugunda bu 10 000 — chegaradan past. 40 000 tugunda esa 20 000 — chegaradan o'tdi. Shundan keyin har shift hamma elementni ko'chiradi — haqiqiy O(n), butun BFS esa O(n²).

Diqqat: Kichik sinovda shift bilan BFS juda tez ko'rinadi — 20 000 tugungacha farq sezilmaydi. Muammo faqat katta ma'lumotda, birdaniga chiqadi. Doim head ko'rsatkichi yoki tayyor navbat tuzilmasini ishlating (Queue va deque).

5.4 Qavatlarni ajratib olish

Ko'pincha qavatlarni alohida-alohida olish kerak: [[50], [30, 70], [20, 40, 60, 80]]. Buning uchun navbatni qavatma-qavat qayta ishlaymiz. Joriy qavat — bitta massiv, uning bolalaridan keyingi qavat yig'iladi:

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 levelSums(root) {
  const sums = [];
  let level = root ? [root] : [];
  while (level.length > 0) {
    let sum = 0;
    const next = [];
    for (const current of level) {
      sum += current.value;
      if (current.left) next.push(current.left);
      if (current.right) next.push(current.right);
    }
    sums.push(sum);
    level = next; // keyingi qavatga o'tamiz
  }
  return sums;
}

console.log(levelSums(root)); // [ 50, 100, 200 ]
console.log(levelSums(null)); // []

Bu yerda shift umuman yo'q: har qavat yangi massiv. Natija — har qavat yig'indisi: 50, 30 + 70, 20 + 40 + 60 + 80.

6. Murakkablik

6.1 Vaqt: hammasi O(n)

Preorder, inorder, postorder va level order — har biri har tugunni bir martadan yozadi va har qirradan bir marta o'tadi. Vaqt O(n). Iterativ preorderni o'lchadik:

n ikki baravar — vaqt ham taxminan ikki baravar. Chiziqli o'sish tasdiqlandi. Birinchi qatordagi kichikroq nisbat — kichik o'lchamda o'lchov shovqini.

6.2 Xotira: shaklga bog'liq

Xotirada farq bor, va u daraxtning shakliga bog'liq:

h — daraxt balandligi, w — eng ko'p tugunli qavatdagi tugunlar soni. To'liq binar daraxtning oxirgi qavatida tugunlarning yarmiga yaqini turadi. Shuning uchun BFS navbati u yerda n ÷ 2 gacha o'sadi. Cho'zilgan daraxtda aksincha: DFS steki n gacha o'sadi, BFS navbatida esa doim bitta tugun.

Iterativ preorder stekida aslida h dan biroz ko'proq tugun turishi mumkin: har pastga tushishda bitta "kutib turgan" o'ng bola qoladi. Lekin baribir O(h).

Tekshirib ko'ring: Kompaniya tuzilmasi: direktorning 1 000 ta bevosita xodimi bor, ularning har birida esa yana 2 tadan yordamchi. Qaysi yurish kamroq xotira oladi — DFS mi, BFS mi?

7. Chegaraviy holatlar

• Bo'sh daraxt (root === null). Rekursiyada to'xtash sharti uni o'zi ushlaydi. Stek va navbatda esa alohida tekshiring — aks holda [null] bilan boshlanadi.
• Bitta tugun. Uchala tartib ham, level order ham bir xil: [7].
• Cho'zilgan daraxt. Rekursiya 11 000–13 800 chuqurlikda yiqildi. Ishonchsiz ma'lumotda (foydalanuvchi yuklagan JSON, chuqur izohlar zanjiri) iterativ variantni tanlang.
• Takroriy qiymatlar. Yurishga ta'sir qilmaydi: biz tugunlarni aylanamiz, qiymatlarni emas. Ikkita "50" ikki marta chiqadi.

8. Ko'p uchraydigan xatolar

8.1 null ni tekshirmaslik

const leaf = { value: 20, left: null, right: null };

function countNodes(node) {
  return 1 + countNodes(node.left) + countNodes(node.right);
}

console.log(countNodes(leaf));

Konsolda:

TypeError: Cannot read properties of null (reading 'left')

Tarjimasi: "null ning xususiyatini o'qib bo'lmaydi (left ni o'qishda)". Funksiya barg ostidagi null ga yetib keldi va undan left ni so'radi. Xabar left ni ko'rsatadi, lekin xato bitta qadam oldin — to'xtash sharti yo'q. Tuzatish: birinchi qatorga if (node === null) return 0; qo'shing.

8.2 Stekka bolalarni noto'g'ri tartibda qo'yish

Preorder uchun chap bola stekka oxirida qo'yiladi. Teskari qo'ysangiz, kod xatosiz ishlaydi, lekin tartib boshqa chiqadi. Tuzatish: "kim birinchi chiqishi kerak — o'shani oxirida qo'yaman" deb eslang.

8.3 BFS da shift

Kichik sinovda sezilmaydi, katta ma'lumotda yuzlab marta sekinlashtiradi. Tuzatish: head ko'rsatkichi yoki qavatma-qavat massivlar.

8.4 Inorderni ko'p bolali daraxtda qidirish

Inorder faqat binar daraxtda ma'noga ega. Menyu, DOM, fayl tizimi uchun preorder yoki postorder tanlang.

9. Mashqlar

1-mashq (oson): Tartiblarni qo'lda yozing

Daraxt: ildiz "osh", chap bola "lag'mon" (uning chap bolasi "manti"), o'ng bola "somsa" (uning o'ng bolasi "chuchvara"). Preorder, inorder, postorder va level order tartiblarini kodsiz yozing.

         osh
        /    \
   lag'mon   somsa
     /           \
  manti        chuchvara

2-mashq (o'rta): Har qavatning eng kattasi

«Bahor» kassalari daraxtga joylashtirilgan: har tugunda — kunlik tushum (ming so'mda). levelMax(root) funksiyasini yozing: har qavatdagi eng katta tushumni qaytarsin. Darsdagi levelSums dan boshlang: yig'indi o'rniga Math.max bilan eng kattasini saqlang. Bo'sh daraxtda — [].

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

function levelMax(root) {
  const result = [];
  let level = root ? [root] : [];
  while (level.length > 0) {
    let max = -Infinity; // manfiy qiymatlar ham bo'lishi mumkin
    const next = [];
    for (const current of level) {
      max = Math.max(max, current.value);
      if (current.left) next.push(current.left);
      if (current.right) next.push(current.right);
    }
    result.push(max);
    level = next;
  }
  return result;
}

const cash = node(900,
  node(1200, node(300)),
  node(450, null, node(-50)));
console.log(levelMax(cash)); // [ 900, 1200, 300 ]
console.log(levelMax(null)); // []

3-mashq (qiyin): Iterativ inorder va testlar

kurs/mashqlar/14/37-yurish/yurish.test.mjs faylida ikki funksiya yozing:

1. inorder(root) — stek bilan, rekursiyasiz. Ishora: "chapga iloji boricha tush, yo'ldagilarni stekka qo'y; keyin stekdan ol, yoz va o'ngga o't" («Inorder va postorder stek bilan» bo'limidagi g'oya).
2. levels(root) — har qavat alohida massivda: [[50], [30, 70], [20, 40, 60, 80]].

Testlar (node:test): bo'sh daraxt, bitta tugun, darsdagi 7 tugunli daraxt va 100 000 chuqurlikdagi cho'zilgan daraxt (stek to'lmasligi kerak).

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

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

function inorder(root) {
  const result = [];
  const stack = [];
  let current = root;
  while (current !== null || stack.length > 0) {
    while (current !== null) {
      stack.push(current); // chapga iloji boricha tushamiz
      current = current.left;
    }
    current = stack.pop(); // chapi tugagan tugun
    result.push(current.value);
    current = current.right; // endi uning o'ng shoxi
  }
  return result;
}

function levels(root) {
  if (root === null) return [];
  const result = [];
  let level = [root];
  while (level.length > 0) {
    result.push(level.map((n) => n.value));
    const next = [];
    for (const n of level) {
      if (n.left) next.push(n.left);
      if (n.right) next.push(n.right);
    }
    level = next;
  }
  return result;
}

const root = node(50,
  node(30, node(20), node(40)),
  node(70, node(60), node(80)));

test("bo'sh daraxt", () => {
  assert.deepEqual(inorder(null), []);
  assert.deepEqual(levels(null), []);
});

test("bitta tugun", () => {
  assert.deepEqual(inorder(node(7)), [7]);
  assert.deepEqual(levels(node(7)), [[7]]);
});

test("7 tugunli daraxt", () => {
  assert.deepEqual(inorder(root), [20, 30, 40, 50, 60, 70, 80]);
  assert.deepEqual(levels(root), [[50], [30, 70], [20, 40, 60, 80]]);
});

test("100 000 chuqurlik — stek to'lmaydi", () => {
  let chain = null;
  for (let i = 100000; i >= 1; i--) chain = node(i, null, chain);
  const values = inorder(chain);
  assert.equal(values.length, 100000);
  assert.equal(values.at(-1), 100000);
  assert.equal(levels(chain).length, 100000);
});

✔ bo'sh daraxt (1.2474ms)
✔ bitta tugun (0.2474ms)
✔ 7 tugunli daraxt (0.1704ms)
✔ 100 000 chuqurlik — stek to'lmaydi (29.9015ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 137.8352

4-mashq: Amaliy tajriba — yurishlar jadvali

kurs/mashqlar/14/MURAKKABLIK.md ga to'rt qator qo'shing: rekursiv DFS, iterativ DFS, BFS (head bilan) va BFS (shift bilan). Xotira ustunida h va w ni ishlating. shift qatorining "Nega" ustuniga o'lchovdagi raqamni yozing.

| Masala | Yechim | Vaqt | Xotira |
|---|---|---|---|
| Daraxtni aylanish | rekursiv DFS | O(n) | O(h) stek |
| Daraxtni aylanish | DFS o'z stekimiz bilan | O(n) | O(h) |
| Qavatma-qavat | BFS, head ko'rsatkichi | O(n) | O(w) |
| Qavatma-qavat | BFS, shift bilan | O(n²) | O(w) |
| Qavatma-qavat | har qavatga qayta DFS | O(n·h) | O(h) |

git add 14/MURAKKABLIK.md 14/37-yurish
git commit -m "14/37: daraxt bo'ylab yurish, iterativ inorder"

10. Real ishda

• Brauzer. DOM — daraxt. querySelectorAll natijasi preorder tartibida. element.contains, closest — daraxt bo'ylab yuqoriga yurish. React kabi kutubxonalar ham komponentlar daraxtini aylanadi (React'ni 17-qismdan o'rganamiz, hozir bilish shart emas).
• Fayl tizimi. Papkalar ro'yxatini chiqarish — preorder; papka hajmini hisoblash va papkani o'chirish — postorder: avval ichidagilar, keyin papkaning o'zi.
• JSON. JSON.stringify obyektni preorder bilan yozadi: avval kalit, keyin uning ichidagi qiymat. Chuqur ichma-ich JSON rekursiv kutubxonalarni yiqitishi mumkin — shuning uchun ishonchsiz ma'lumotda chuqurlik chegarasi qo'yiladi.
• Graflar. Xuddi shu DFS va BFS graflarda ham ishlaydi — faqat "ko'rilganlar" to'plami qo'shiladi.
• Intervyu. "Daraxtni qavatma-qavat chiqaring", "rekursiyasiz inorder yozing", "daraxtning chap ko'rinishini toping" — eng ko'p so'raladigan daraxt masalalari.

Xulosa

• DFS bitta shoxni oxirigacha tushadi, BFS qavatma-qavat yuradi.
• Rekursiv yurish har tugunga uch marta keladi: kelganda yozsak — preorder, chapdan qaytganda — inorder, o'ngdan qaytganda — postorder.
• Rekursiya cho'zilgan daraxtda (11 000–13 800 chuqurlik) Maximum call stack size exceeded beradi; o'z stekimiz bilan iterativ yurish bunday chegarasiz.
• BFS — navbat bilan, head ko'rsatkichi orqali. shift navbat ~16 000 elementdan uzunlashganda O(n) bo'lib, BFS ni 550 baravar sekinlashtirdi.
• Hamma yurish — O(n) vaqt. Xotira: DFS — O(h), BFS — O(w).

Keyingi dars: Binary Search Tree — inorder nega o'sish tartibida chiqdi: "chapda kichik, o'ngda katta" qoidasi bilan qidirish, qo'shish va o'chirish.

Manbalar

• Thomas H. Cormen va boshq., "Introduction to Algorithms", 4-nashr, MIT Press, 2022 — 12-bob (daraxt bo'ylab yurish), 20-bob (BFS, DFS).
• MDN: Array.prototype.shift(), Document.querySelectorAll() ("document order") — developer.mozilla.org
• V8 manba kodi: Heap::LeftTrimFixedArray — kichik massivda shift uchun boshini kesish — github.com/v8/v8