Daraxt chuqurligi

Binar daraxt berilgan. Uning maksimal chuqurligini toping.

Maksimal chuqurlik — ildizdan eng chuqur bargigacha bo'lgan tugunlar soni.

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

Chiqish: 3

Ildizdan [15] yoki [7] gacha: [3] → [20] → [15] — 3 ta tugun. Bu maksimal yo'l.

Kirish:

[1]
  \
  [2]

Chiqish: 2

Kirish: (bo'sh daraxt)

Chiqish: 0

Asosiy g'oya: rekursiya

Ildizning maksimal chuqurligi qanday? U 1 (ildizning o'zi) va chap yoki o'ng kenja daraxtning maksimal chuqurligidan kattasi yig'indisi:

DEPTH(root) = 1 + MAX(DEPTH(root.left), DEPTH(root.right))

Base case: bo'sh daraxt uchun chuqurlik 0.

FUNCTION MAX_DEPTH(node)
    IF node = NULL
        RETURN 0

    left_depth  = MAX_DEPTH(node.left)
    right_depth = MAX_DEPTH(node.right)

    RETURN 1 + MAX(left_depth, right_depth)

Bu postorder rekursiya: avval kenja daraxtlar hisoblanadi, so'ng natijalar birlashtirilib qaytariladi.

Bosqichma-bosqich dry run

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

Rekursiv chaqiruvlar zanjirini kuzatamiz:

MAX_DEPTH(3):
  MAX_DEPTH(9):
    MAX_DEPTH(NULL) = 0   (9 ning chap bolasi)
    MAX_DEPTH(NULL) = 0   (9 ning o'ng bolasi)
    return 1 + MAX(0, 0) = 1
  MAX_DEPTH(20):
    MAX_DEPTH(15):
      MAX_DEPTH(NULL) = 0
      MAX_DEPTH(NULL) = 0
      return 1 + MAX(0, 0) = 1
    MAX_DEPTH(7):
      MAX_DEPTH(NULL) = 0
      MAX_DEPTH(NULL) = 0
      return 1 + MAX(0, 0) = 1
    return 1 + MAX(1, 1) = 2
  return 1 + MAX(1, 2) = 3

Javob: 3

Har tugun faqat bir marta ko'riladi. Har rekursiv chaqiruv O(1) ish bajaradi.

Iterativ yondashuv: BFS

Rekursiya o'rniga BFS bilan qavatma-qavat sanash. Qavatlar soni — maksimal chuqurlik.

FUNCTION MAX_DEPTH_BFS(root)
    IF root = NULL
        RETURN 0

    queue = [root]
    depth = 0

    WHILE queue bo'sh emas
        depth = depth + 1
        level_size = navbat hajmi

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

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

    RETURN depth

Dry run:

queue: [3]     depth: 0

Iteratsiya 1: level_size=1
  DEQUEUE 3 → 20, 9 qo'shildi
  queue: [9, 20]    depth: 1

Iteratsiya 2: level_size=2
  DEQUEUE 9 → bolasi yo'q
  DEQUEUE 20 → 15, 7 qo'shildi
  queue: [15, 7]    depth: 2

Iteratsiya 3: level_size=2
  DEQUEUE 15 → bolasi yo'q
  DEQUEUE 7 → bolasi yo'q
  queue: []    depth: 3

Javob: 3

Vaqt va xotira murakkabligi

Yondashuv	Vaqt	Xotira	Eslatma
Rekursiv DFS	O(n)	O(h)	Call stack chuqurligi
Iterativ BFS	O(n)	O(w)	Eng keng qavat

n — tugunlar soni, h — balandlik, w — eng keng qavat.

Muvozanatlangan daraxtda: rekursiv O(log n) xotira, BFS O(n/2) = O(n) xotira — rekursiv afzalroq.

Muvozanatsiz (zanjir) daraxtda: rekursiv O(n) xotira (stack overflow xavfi!), BFS O(1) xotira — BFS afzalroq.

Minimal chuqurlik

Ba'zan ildizdan eng yaqin barggacha bo'lgan yo'l so'raladi — minimal chuqurlik.

        [1]
       /   \
     [2]   [3]
    /
  [4]

Maksimal chuqurlik: 3 (1 → 2 → 4). Minimal chuqurlik: 2 (1 → 3).

Muhim farq: [2] ning faqat chap bolasi bor. [2] barg emas — uning bolasi bor. Minimal chuqurlik bargga bo'lgan eng qisqa yo'l.

FUNCTION MIN_DEPTH(node)
    IF node = NULL
        RETURN 0

    // Bitta bolasi bo'lgan tugun barg hisoblanmaydi
    IF node.left = NULL
        RETURN 1 + MIN_DEPTH(node.right)
    IF node.right = NULL
        RETURN 1 + MIN_DEPTH(node.left)

    RETURN 1 + MIN(MIN_DEPTH(node.left), MIN_DEPTH(node.right))

Nima uchun faqat 1 + MIN(left, right) emas? Agar chap bola bo'lmasa, MIN_DEPTH(NULL) = 0 qaytaradi — bu noto'g'ri, chunki NULL barg emas.

Edge case'lar

Bo'sh daraxt. root = NULL → return 0. Avval tekshirilishi kerak.

Bitta tugunli daraxt (faqat ildiz). Chap va o'ng NULL → 1 + MAX(0, 0) = 1. To'g'ri.

Faqat chap yoki o'ng shox. Zanjir ko'rinishidagi daraxt: 1 → 2 → 3 → 4. Chuqurlik 4. Rekursiya har qadam 1 + MAX(0, chuqurlik) hisoblaydi.

Muvozanatsiz daraxt. Chuqur shox maksimumni belgilaydi — bu to'g'ri ishlaydi.

Note

chuqurlik va balandlik atamalari ba'zan aralashtiriladi. Bu masalada "maksimal chuqurlik" so'ralsa ham, aslida ildizning balandligi + 1 hisoblanadi. Ko'p platformalarda "maximum depth = number of nodes along the longest path" deyiladi — bu tugunlar soni, qirralar soni emas.

Masalaning kengaytirilgan varianti

Muvozanatlangan daraxtni tekshirish. Har tugun uchun chap va o'ng kenja daraxt balandliklari farqi 1 dan oshmasligini tekshirish — chuqurlik rekursiyasining kengaytmasi.

FUNCTION IS_BALANCED(node)
    IF node = NULL
        RETURN TRUE

    left_h  = HEIGHT(node.left)
    right_h = HEIGHT(node.right)

    IF ABS(left_h - right_h) > 1
        RETURN FALSE

    RETURN IS_BALANCED(node.left) AND IS_BALANCED(node.right)

Bu O(n²) — har tugun uchun balandlik hisoblanadi. Optimallashtirilgan versiyada balandlik va muvozanatlilik bir rekursiyada birgalikda hisoblanadi.

Xulosa

Maksimal chuqurlik — rekursiyaning klassik namunasi. Har tugun o'z kenja daraxtlarining chuqurligini so'raydi va birini qo'shib qaytaradi.

Ikkita yondashuv: rekursiv DFS (kod sodda, xotira O(h)) va iterativ BFS (qavatlarni sanash, xotira O(w)). Muvozanatlangan daraxtda DFS afzal; katta muvozanatsiz daraxlarda BFS stack overflow xavfidan xoli.

Asosiy tuzilma — return 1 + MAX(left, right) — daraxt masalalarida qayta-qayta uchraydi: balandlik hisoblash, muvozanatni tekshirish, eng uzun yo'l topish.