3.4.1
Tree ek aisa tarika hai data organize karne ka jo ek family tree ya company org chart ki tarah branch karta hai — upar ek boss, neeche employees, unke neeche sub-employees, aur koi loop nahi (tum kabhi apne hi subordinate ko report nahi karte). Neeche ki vocabulary bas "kaun kahan hai" ke precise naam hain us hierarchy mein. Jab ye naam click ho jaayein, har tree algorithm readable ho jaata hai.
Tree nodes ka ek collection hai jo edges se connected ho, is tarah ki:
exactly ek special node hota hai jise root kehte hain,
baaki har node ka exactly ek parent hota hai,
koi cycles nahi hote (koi path apne aap mein loop nahi karta).
n == n − 1 ==
n − 1 n − 1 n − 1 derived hai, memorize nahi karna.
Root ::: sabse upar wala akela node, sirf wahi ek jiska koi parent nahi hota.Leaf (external node) ::: woh node jiska koi child nahi hota.Internal node ::: woh node jiska kam se kam ek child ho (jo leaf nahi hai).Parent / Child ::: agar edge A B A B Siblings ::: woh nodes jo ek hi parent share karte hain.Ancestor ::: koi bhi node jo kisi node se root tak ke path par ho.Descendant ::: kisi given node ke neeche wala koi bhi node.Degree of a node ::: uske children ki sankhya.Degree of a tree ::: us mein kisi bhi node ki maximum degree .Subtree ::: ek node aur uske saare descendants , jise apne aap mein ek tree maana jaaye.
Intuition KYU do alag measures?Depth jawaab deta hai "main boss (root) se kitna door hoon?" — tum upar dekhke measure karte ho.
Height jawaab deta hai "mere neeche sabse gehra worker kitna door hai?" — tum neeche dekhke measure karte ho.
Ye mirror questions hain, isliye log inhe swap kar dete hain. Inhe arrow ki direction se seedha rakho.
Definition Depth aur Height
Depth of node v ::: root se v == 0 == Height of node v ::: v leaf tak ke sabse lambe path par edges ki sankhya.
Har leaf ki height == 0 == Height of the tree ::: uske root ki height (= kisi bhi node ki max depth).
Worked example Example tree A <- depth 0
/ | \
B C D <- depth 1
/ \ \
E F G <- depth 2
\
H <- depth 3
Q: Root? → A. Ye step KYU? Ye akela node hai jiska koi parent nahi.
Q: Leaves? → E, F, C, H. KYU? Inke koi children nahi hain. (Dhyaan do C depth 1 par bhi leaf hai — leaf ≠ sabse gehra!)
Q: Degree of A? → 3 (children B, C, D). Degree of the tree? → 3 (A ka max hai).
Q: Depth of H? → 3. KYU? Path A→D→G→H mein 3 edges hain.
Q: Height of D? → 2. KYU? Neeche sabse lamba path: D→G→H = 2 edges.
Q: Height of the tree? → 3 (= root A ki height, sabse lamba root-to-leaf path A→D→G→H).
Q: Subtree rooted at D? → nodes {D, G, H} D ke saath uske local root ki tarah.
Worked example Height recursively compute karo (algorithm ko Feynman karo)Apply height ( v ) = 1 + max ( children heights )
h ( E ) = h ( F ) = h ( C ) = h ( H ) = 0 KYU? Koi children nahi.h ( G ) = 1 + h ( H ) = 1 KYU? G ka akela child H height 0 ka hai.h ( B ) = 1 + max ( h ( E ) , h ( F )) = 1 + 0 = 1 h ( D ) = 1 + h ( G ) = 1 + 1 = 2 h ( A ) = 1 + max ( h ( B ) , h ( C ) , h ( D )) = 1 + max ( 1 , 0 , 2 ) = 3
Common mistake "Leaf hamesha sabse neeche wale level par hona chahiye."KYU sahi lagta hai: Leaves aksar nice balanced trees mein sabse gehra level par hoti hain, toh brain "leaf" ko "sabse gehra" se jod leta hai.
Fix: Leaf ko sirf koi child na hone se define kiya jaata hai. Example mein, C depth 1 par leaf hai jabki H depth 3 par leaf hai. Leaf = koi kids nahi, bas itna.
Common mistake "Height aur depth ek hi number hain."KYU sahi lagta hai: Root ke liye, tree ki height = max depth, toh wahan dono coincide karte hain.
Fix: Ye opposite directions measure karte hain. Depth root tak upar count karta hai; height sabse gehari leaf tak neeche count karta hai. Ek generic node ke liye ye alag hote hain.
Common mistake "Root ki depth 1 hoti hai" / "Leaf ki height 1 hoti hai."KYU sahi lagta hai: Hum naturally 1 se count shuru karte hain.
Fix: Hum edges count karte hain, nodes nahi. Root: apne tak 0 edges → depth 0. Leaf: neeche 0 edges → height 0. (Kuch textbooks nodes count karte hain; hamesha apna convention batao . Ye note edge convention use karta hai.)
Common mistake "Degree matlab ek node ko touch karne wale edges ki sankhya (like graphs)."KYU sahi lagta hai: Graph theory mein degree = total incident edges.
Fix: Trees mein, degree usually = children ki sankhya (sirf neeche ke edges), parent edge ko ignore karke.
Recall Ek 12-saal ke bachhe ko explain karo (hidden)Socho ek family tree ulta draw kiya gaya hai. Bilkul upar great-grandparent hai, woh root hai. Jinka koi bachha nahi hai woh leaves hain. Tumhari depth hai kitne steps upar chalna padega top boss tak pahunchne ke liye. Tumhari height hai tumhari branch mein sabse door ke bachhe tak kitne steps neeche jaana padega. Degree bas hai tumhare kitne direct children hain. Subtree hai "tum aur tumhare neeche poori family line" — yeh apne aap mein ek chhota tree hai. Koi apna khud ka ancestor nahi ho sakta, isliye koi loops nahi hote!
D epth → D own from the root (upar se count karo). Root = 0.H eight → H ow far to the bottom leaf. Leaf = 0."Leaf = Leave-less " (usse koi child leave nahi karta).
"Tree degree = sabse zyada boss node ka child-count."
n n − 1
Leaf ki definition? A node with no children.
Root ki definition? Woh akela node jiska koi parent nahi hota; sabse upar wala node.
Root ki depth kya hoti hai? 0 (root se apne tak zero edges).
Leaf ki height kya hoti hai? 0 (usse neeche leaf tak zero edges — khud hi leaf hai).
Depth vs height, ek ek line mein? Depth = root tak upar edges; Height = sabse gehari leaf tak neeche edges.
Node v ki height ka recursive formula? height ( v ) = 1 + max c height ( c ) = 0
Node ki degree vs tree ki degree? Node degree = uske children ki sankhya; tree degree = sabhi nodes mein max degree.
Subtree kya hota hai? A node together with all its descendants, viewed as a tree on its own.
Kya leaf bottom level se upar appear ho sakta hai? Haan — leaf matlab "koi children nahi", jo kisi bhi depth par ho sakta hai.
Height h ≤ d d ≥ 2 d − 1 d h + 1 − 1 d 0 + ⋯ + d h
Poore tree ki height barabar hoti hai? Height of the root = max depth among all nodes.
Binary Trees — special case jahan tree ki degree ≤ 2 Binary Search Trees — is terminology par based ordering invariant.Tree Traversals — DFS/BFS nodes ko depth/level ke hisaab se visit karte hain.Balanced Trees (AVL, Red-Black) — height control karte hain taaki operations O ( log n ) Recursion — height/subtree definitions inherently recursive hain.Graphs — tree ek connected acyclic graph hai; degree definitions compare karo.
