Daraxt qavatlari (Level Order Traversal)

Binar daraxt berilgan. Uni qavat bo'yicha o'qing: har qavatdagi tugun qiymatlarini alohida ro'yxatda qaytaring.

Kirish:
        [3]
       /   \
     [9]   [20]
           / \
         [15] [7]

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

Ildiz birinchi qavat, uning bolalari ikkinchi, va hokazo. Har qavat chapdan o'ngga tartibda o'qiladi.

Asosiy g'oya: BFS

Daraxtni qavatma-qavat o'qish — BFS (Breadth-First Search)ning tabiiy vazifasi. Navbat (queue) ishlatiladi.

Muammo: navbatda turli qavatlar tugunlari aralashmasligi kerak. Yechim: navbatga qo'shishdan oldin joriy qavatdagi tugunlar sonini level_size sifatida saqlaymiz. Faqat shu sondagi tugunlarni qayta ishlaymiz.

FUNCTION LEVEL_ORDER(root)
    IF root = NULL
        RETURN []

    result = []
    queue = [root]

    WHILE queue bo'sh emas
        level_size = navbat hajmi    // joriy qavat tugunlari soni
        current_level = []

        FOR i = 0 DAN level_size-1 GACHA
            node = queue dan DEQUEUE

            current_level ga node.value qo'sh

            IF node.left ≠ NULL
                queue ga node.left ENQUEUE
            IF node.right ≠ NULL
                queue ga node.right ENQUEUE

        result ga current_level qo'sh

    RETURN result

Bosqichma-bosqich dry run

        [3]
       /   \
     [9]   [20]
           / \
         [15] [7]

queue: [3]    result: []

Iteratsiya 1 (qavat 0):
  level_size = 1
  DEQUEUE [3]:
    current_level: [3]
    ENQUEUE [9], [20]
  queue: [9, 20]
  result: [[3]]

Iteratsiya 2 (qavat 1):
  level_size = 2
  DEQUEUE [9]:
    current_level: [9]
    bolasi yo'q → navbatga hech narsa qo'shilmaydi
  DEQUEUE [20]:
    current_level: [9, 20]
    ENQUEUE [15], [7]
  queue: [15, 7]
  result: [[3], [9, 20]]

Iteratsiya 3 (qavat 2):
  level_size = 2
  DEQUEUE [15]:
    current_level: [15]
    bolasi yo'q
  DEQUEUE [7]:
    current_level: [15, 7]
    bolasi yo'q
  queue: []
  result: [[3], [9, 20], [15, 7]]

WHILE sharti: queue bo'sh → chiqish

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

Nima uchun level_size muhim?

level_size olmay, shunchaki navbatda element bo'lguncha dequeue qilsak nima bo'ladi?

queue: [3]

DEQUEUE [3] → ENQUEUE [9], [20]
queue: [9, 20]

DEQUEUE [9] → bolasi yo'q
DEQUEUE [20] → ENQUEUE [15], [7]
queue: [15, 7]

...

Bu barcha elementlarni to'g'ri tartibda beradi, lekin qavatlarni ajratib bo'lmaydi. level_size iteratsiya boshida saqlanadi — shu moment'dagi navbat hajmi aynan joriy qavat.

Teskari qavat tartibi

Ba'zan pastdagi qavatdan yuqoriga — teskari tartibda qavat ro'yxati kerak bo'ladi:

Kirish:         Chiqish: [[15, 7], [9, 20], [3]]
        [3]
       /   \
     [9]   [20]
           / \
         [15] [7]

Yechim: BFS natijasini teskari tartibga sol.

FUNCTION LEVEL_ORDER_BOTTOM(root)
    result = LEVEL_ORDER(root)
    result ni teskari tartibga sol
    RETURN result

Yoki BFS davomida result boshiga qo'shish (ko'plab tuzilmalarda samarasiz — ro'yxat oxiriga qo'shib, oxirida teskarilash afzal).

O'ngdan chapga qavat

Har qavatdagi elementlarni o'ngdan chapga tartibda o'qish. BFS-ning o'zgarmagan versiyasida chapdan o'ngga. O'ngdan chapga uchun stek yordamida yoki har qavat natijasini teskari qilish:

  FOR i = 0 DAN level_size-1 GACHA
      node = queue dan DEQUEUE

      // O'ngdan chapga: bolalarni o'ng → chap tartibda qo'sh
      IF node.right ≠ NULL
          queue ga node.right ENQUEUE
      IF node.left ≠ NULL
          queue ga node.left ENQUEUE

      current_level ga node.value qo'sh

Zigzag qavat traversali

Har qavat galma-galma chapdan o'ng, o'ngdan chapga o'qiladi:

Kirish:             Chiqish: [[3], [20, 9], [15, 7]]
        [3]
       /   \
     [9]   [20]
           / \
         [15] [7]

Tartib: qavat 0 — chapdan o'ng, qavat 1 — o'ngdan chap, qavat 2 — chapdan o'ng, ...

FUNCTION ZIGZAG_LEVEL_ORDER(root)
    IF root = NULL
        RETURN []

    result = []
    queue = [root]
    left_to_right = TRUE

    WHILE queue bo'sh emas
        level_size = navbat hajmi
        current_level = []

        FOR i = 0 DAN level_size-1 GACHA
            node = queue dan DEQUEUE
            current_level ga node.value qo'sh

            IF node.left ≠ NULL
                queue ga node.left ENQUEUE
            IF node.right ≠ NULL
                queue ga node.right ENQUEUE

        IF NOT left_to_right
            current_level ni teskari tartibga sol

        result ga current_level qo'sh
        left_to_right = NOT left_to_right

    RETURN result

Vaqt va xotira murakkabligi

Amal	Vaqt	Xotira
Level order	O(n)	O(w)

n — tugunlar soni, w — eng keng qavat.

Navbatda bir vaqtda ko'pi bilan ikki qavat tugunlari turadi. Mukammal binar daraxtning oxirgi qavati n/2 tugun saqlaydi → xotira O(n).

Edge case'lar

Bo'sh daraxt. root = NULL → return []. Ro'yxat bo'sh.

Bitta tugunli daraxt. [[root.value]] — bitta qavat, bitta element.

Faqat chap shox (zanjir). Har qavatda bitta element. [[1], [2], [3], [4]].

Mukammal binar daraxt. Har qavat to'la. Oxirgi qavat n/2 element.

Bir xil qiymatli tugunlar. Qiymatlar == emas, tuzilma muhim. BFS tartibni saqlab, to'g'ri natija beradi.

Note

level_size navbatga yangi element qo'shishdan oldin olinishi muhim. Agar tsikl ichida navbat hajmi dinamik o'lchansa va bir vaqtda yangi elementlar qo'shilsa — shart to'g'ri bajarilmaydi.

Real qo'llanishlar

Grafda eng qisqa yo'l

BFS grafda ham ishlaydi. Manbadan BFS qilsak, birinchi topilgan yo'l doim eng qisqa (qirra soni bo'yicha). Level order traversal bu tushunchaning daraxtdagi versiyasi.

Daraxt tasvirini chizish

UI'da daraxtni tasvirlamoqchi bo'lganda, level order traversal qavatlarni to'g'ri joylashtirish uchun ishlatiladi.

Daraxt tekshirish

"Barcha barglar bir xil qavatta ekanmi?" — BFS bilan oson: oxirgi qavat elementlari barg bo'lishi kerak.

Serialization

Daraxtni saqlash yoki uzatish uchun level order ketma-ketligi (NULL qiymatlar bilan) daraxtni to'liq tiklashga imkon beradi.

DFS bilan qavat order solishtirish

Level order masalasini DFS bilan ham yechish mumkin — har tugunning qavat indeksini argument sifatida uzatib:

FUNCTION DFS_LEVEL_ORDER(node, level, result)
    IF node = NULL
        RETURN

    IF level = result hajmi
        result ga [] qo'sh      // yangi qavat

    result[level] ga node.value qo'sh

    DFS_LEVEL_ORDER(node.left,  level + 1, result)
    DFS_LEVEL_ORDER(node.right, level + 1, result)

Bu DFS bilan level order natijasini hosil qiladi. BFS versiyasiga qaraganda xotira O(h) (qavat hajmi o'rniga balandlik). Lekin BFS qavat intuitiv va samaraliroq.

Xulosa

Level Order Traversal BFS yordamida qavatma-qavat o'qishni amalga oshiradi. Kalit element — level_size: tsikl boshida navbat hajmini qat'iy saqlab, faqat joriy qavat elementlarini qayta ishlash.

Teskari qavat, zigzag, o'ngdan chapga kabi variantlar bir xil BFS skelet ustiga kichik o'zgarishlar bilan quriladi.

BFS'ning eng kuchli tomoni — minimal qavat chuqurligida element topish va "barcha qo'shnilarni avval ko'rib chiqish" — grafda ham, daraxtda ham bir xil mantiqda ishlaydi.