Clinic #09 - Maximum Depth of Binary Tree

Pattern: Tree Recursion (DFS) · LC 104

Ek family register jaisa naksha: sabse upar ek naam, uske neeche do naam, unke neeche phir do-do, jab tak record khatam na ho jaaye. Sawaal seedha hai - sabse lambi confirmed line kitni generations tak jaati hai?

Before you start. Itna kaafi hai: upar ek box hota hai, uske neeche zyada se zyada do box latak sakte hain, aur yehi shape neeche tak dohrati hai. Foundations #08 - Trees & Recursion isi shape pe poora saancha sikhata hai; yahan sirf ek specific sawaal us saanche se solve hoga.

Ek genealogist (family history ka record rakhne wala insaan) apna purana family register kholta hai, kisi reunion ke liye. Sabse upar ek naam hai - parivaar ka sabse purana insaan jiska record bacha hai. Uske do bete likhe hain, dono ke aage apne-apne bete, aur wahi silsila neeche chalta hai. Kuch lines bahut lambi chalti hain - pardada, unke bete, unke bete, saat generations tak record milta hai. Kuch beech mein hi ruk jaati hain - kisi bete ka aage koi record nahi mila, register wahi khatam ho jaata hai.

Genealogist ek cheez jaanna chahta hai: sabse lambi confirmed line kitni generations tak jaati hai, register ke saare beton mein se. Register ka har naam engineer ke liye ek node hai, aur har node ke neeche zyada se zyada do node hote hain - bete A, bete B. Isi shape ko engineers binary tree bulate hain. Board ka udaharan bhi yehi hai:

      3
     / \
    9   20        ->   depth = 3   (3 -> 20 -> 15/7)
        / \
       15  7

Jiske aage koi record nahi bacha uski jagah null likhi jaati hai - 9 ke neeche dono taraf null hai, isliye 9 ki line wahi khatam. Sabse lambi line root (3) se sabse door node tak jitne node hain, wahi is sawaal ka jawab hai: max depth.