PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम Tree Terminology: Root, Node, Parent, Child, Siblings, Leaf (ट्री शब्दावली: रूट, पैरेंट, चाइल्ड, पत्ती (लीफ) और सिबलिंग्स) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।
Overview: A Tree is a non-linear hierarchical data structure consisting of V nodes connected by exactly V - 1 acyclic edges descending from a unique topmost Root node. Core terminology categorizes relationships unambiguously: Parent/Child links, Siblings sharing the exact same parent, external Leaf nodes with zero children, and internal nodes with at least one child.
अध्याय सार: ट्री (Tree) एक गैर-रैखिक पदानुक्रमित डेटा संरचना है जिसमें V नोड्स बिना किसी चक्र (cycle) के ठीक V - 1 एजेस द्वारा एक अद्वितीय शीर्ष Root नोड से जुड़े रहते हैं। इसकी मूल शब्दावली में Parent-Child संबंध, एक ही पैरेंट वाले Siblings, शून्य बच्चों वाले Leaf (बाह्य) नोड्स और कम से कम 1 बच्चे वाले आंतरिक नोड्स शामिल हैं।
Tree Terminology: Root, Node, Parent, Child, Siblings, Leaf: Detailed Notes & Architecture (ट्री शब्दावली: रूट, पैरेंट, चाइल्ड, पत्ती (लीफ) और सिबलिंग्स)
1. Non-Linear Hierarchy, Root Node, and the V - 1 Edges Invariant (गैर-रैखिक पदानुक्रम, रूट नोड और V - 1 एजेस नियम)
[EN] Unlike linear structures (Arrays, Stacks, Queues) where items follow a single predecessor-successor sequence, a Tree organizes data hierarchically. Every non-empty tree contains exactly one Root node having zero parents (in-degree 0), while every other node has exactly one incoming edge from a unique parent. Because a tree is a connected acyclic graph, any tree with V nodes always possesses exactly V - 1 edges and a single unique simple path between any two nodes.
[HI] एरे या कतार जैसी रैखिक संरचनाओं के विपरीत, ट्री डेटा को श्रेणीबद्ध (Hierarchical) रूप में व्यवस्थित करता है। किसी गैर-खाली ट्री में शीर्ष पर ठीक एक Root नोड होता है जिसका कोई पैरेंट नहीं होता, जबकि हर अन्य नोड का ठीक एक पैरेंट होता है। चूंकि ट्री एक बिना चक्र (acyclic) जुड़ा हुआ ग्राफ है, इसलिए V नोड्स वाले ट्री में हमेशा ठीक V - 1 एजेस होती हैं।
2. Parent, Child, and Siblings vs Cousins Distinction (पैरेंट, चाइल्ड और सिबलिंग्स बनाम कजिन्स में अंतर)
[EN] When an edge connects upper node P directly downward to lower node C, P is the Parent of C and C is a Child of P. Nodes that share the exact same immediate Parent are termed Siblings (brothers). A common competitive-exam trap equates 'same level' with 'siblings': nodes sitting at the same horizontal level but descending from different parents are Cousins, NOT Siblings.
[HI] जब किसी एज द्वारा ऊपरी नोड P सीधे निचले नोड C से जुड़ता है, तो P को C का Parent और C को P का Child कहते हैं। वे नोड्स जिनका सीधा Parent एक ही हो, उन्हें Siblings कहा जाता है। परीक्षा में अक्सर एक भ्रम पूछा जाता है: समान लेवल पर होने मात्र से दो नोड्स Siblings नहीं बन जाते—यदि उनके पैरेंट अलग हैं, तो वे कजिन्स होते हैं, सिबलिंग्स नहीं।
3. Leaf (External) Nodes vs Internal (Non-Terminal) Nodes (पत्ती (Leaf / बाह्य) नोड्स बनाम आंतरिक नोड्स)
[EN] A Leaf node (also called External or Terminal node) is any node having zero children (out-degree = 0). Conversely, an Internal node (Non-Terminal node) is any node having at least one child (out-degree >= 1). Notably, in a degenerate tree containing only a single node (the Root by itself), that Root has 0 children and therefore qualifies simultaneously as a Leaf node.
[HI] वह नोड जिसकी कोई संतान (Child) न हो, उसे Leaf (पत्ती, External या Terminal) नोड कहते हैं। इसके विपरीत, जिस नोड का कम से कम एक बच्चा हो, वह Internal (आंतरिक) नोड कहलाता है। ध्यान दें कि यदि किसी ट्री में केवल 1 ही नोड (अकेला Root) हो, तो उसका कोई बच्चा न होने के कारण वह Root स्वयं एक Leaf नोड भी होता है।
4. Ancestors, Descendants, Subtrees, and Forests (पूर्वज (Ancestors), वंशज (Descendants), सबट्री और फॉरेस्ट)
[EN] Every node lying on the unique path from the Root down to node X (excluding or including X depending on strict vs non-strict convention; strictly above X) is an Ancestor of X, while all nodes contained inside the downward hierarchy rooted at X are Descendants of X. Any node along with all its descendants forms a valid recursive Subtree. Deleting the Root node along with its incident edges splits a single tree into a Forest—a collection of disjoint trees.
[HI] रूट से किसी नोड X तक जाने वाले रास्ते में आने वाले सभी ऊपरी नोड्स X के Ancestors (पूर्वज) और X के नीचे जुड़े सभी नोड्स X के Descendants (वंशज) कहलाते हैं। किसी नोड और उसके सभी वंशजों से मिलकर एक स्वतंत्र Subtree बनता है। यदि किसी ट्री से रूट नोड हटा दिया जाए, तो शेष असंबद्ध ट्रीज का समूह Forest (जंगल) कहलाता है।
Syntax, Formula & Technical Example (Tree Terminology: Root, Node, Parent, Child, Siblings, Leaf)
[A] <- Root (Parent of B, C; Internal)
/ \
[B] [C] <- B & C are Siblings; C is a Leaf
/ \
[D] [E] <- D & E are Siblings & Leaves
// Count check: Nodes V = 5 (A,B,C,D,E) -> Edges = V - 1 = 4
// Ancestors of D: {B, A} | Descendants of B: {D, E}
Tree Terminology: Root, Node, Parent, Child, Siblings, Leaf Quick Reference & Comparison Table
| Tree Term | Exact Structural Definition | Key Exam Fact |
|---|---|---|
| Root Node | Unique topmost node having zero parents | Every non-empty tree has exactly one root |
| Leaf (External) Node | Node having zero children (out-degree = 0) | Single-node tree's root is also a leaf |
| Siblings | Two or more nodes sharing the exact same parent | Same level with different parents are NOT siblings |
| Internal Node | Node possessing at least one child node | Root is internal whenever tree size > 1 |
Tree Terminology: Root, Node, Parent, Child, Siblings, Leaf Top 20 Bilingual MCQs with Answers
Q1. How many edges are always present in any connected tree containing exactly 25 nodes?
(ठीक 25 नोड्स वाले किसी भी जुड़े हुए ट्री में हमेशा कुल कितनी एजेस (Edges) होंगी?)
(A) 24
(B) 25
(C) 26
(D) 50
Correct Answer: (A)
[EN] Any tree on V vertices is minimally connected and acyclic, containing strictly V - 1 = 25 - 1 = 24 edges.
[HI] V नोड्स वाले प्रत्येक ट्री में ठीक V - 1 एजेस होती हैं, अतः 25 - 1 = 24 एजेस होंगी।
Q2. What strictly qualifies two nodes X and Y in a tree as 'Siblings'?
(किसी ट्री में दो नोड्स X और Y को 'Siblings' कब कहा जाता है?)
(A) X and Y contain identical data keys
(B) X and Y are both Leaf nodes
(C) X and Y sit at the same depth/level regardless of parent
(D) X and Y have the exact same immediate Parent node
Correct Answer: (D)
[EN] Siblings must share the identical parent; nodes on the same level with different parents are merely cousins.
[HI] जब दो नोड्स का सीधा Parent एक ही हो तब वे Siblings होते हैं; केवल एक ही लेवल पर होना पर्याप्त नहीं है।
Q3. What defines a Leaf (External / Terminal) node in a tree?
(ट्री में Leaf (बाह्य/टर्मिनल) नोड की सटीक परिभाषा क्या है?)
(A) A node with at least one child
(B) Only nodes located at maximum tree height
(C) A node with zero children (out-degree = 0)
(D) Any node other than the Root
Correct Answer: (C)
[EN] Any node having no children is a leaf, even if it sits near the top of the tree (e.g., an empty branch right under root).
[HI] वह प्रत्येक नोड जिसकी एक भी संतान (Child) न हो, Leaf नोड कहलाता है—चाहे वह कम गहराई पर ही क्यों न हो।
Q4. In a tree containing ONLY one node (just the Root R), how is node R classified?
(यदि किसी ट्री में केवल एक ही नोड (अकेला रूट R) हो, तो R किस श्रेणी में आता है?)
(A) A Forest
(B) An Internal node only
(C) Neither Root nor Leaf
(D) Both a Root node and a Leaf (External) node
Correct Answer: (D)
[EN] R is the topmost node (Root) and simultaneously has 0 children (Leaf).
[HI] अकेला नोड शीर्ष होने से Root है और शून्य बच्चे होने के कारण Leaf (बाह्य) नोड भी है।
Q5. What data structure results when you delete the Root node (and its edges) from a tree whose Root had 3 children?
(यदि 3 बच्चों वाले रूट नोड को ट्री से हटा दिया जाए, तो शेष बचे असंबद्ध ट्रीज के समूह को क्या कहते हैं?)
(A) A Circular Linked Graph
(B) A Forest of 3 disjoint trees
(C) A Single Connected Tree
(D) A Complete Bipartite Graph
Correct Answer: (B)
[EN] Removing the root splits the tree into a collection of zero or more disjoint trees known as a Forest.
[HI] रूट हटने पर बचे हुए स्वतंत्र सब-ट्रीज का संग्रह Forest कहलाता है।
Q6. In the tree where A is parent of B and C, B is parent of D and E, and C is parent of F, which pair are Siblings vs NOT Siblings?
(ट्री में A के बच्चे B व C हैं; B के बच्चे D व E हैं; C का बच्चा F है। इनमें से कौन सा जोड़ा Siblings है और कौन सा नहीं?)
(A) E & F are Siblings; B & C are NOT Siblings
(B) D & F are Siblings
(C) D & E are Siblings; E & F are NOT Siblings
(D) A & B are Siblings
Correct Answer: (C)
[EN] D and E share parent B (siblings), whereas E (parent B) and F (parent C) have different parents despite sharing level 2.
[HI] D व E का पैरेंट B है इसलिए वे Siblings हैं, जबकि E (पैरेंट B) व F (पैरेंट C) समान लेवल पर होकर भी Siblings नहीं हैं।
Q7. How many unique simple paths exist between any two distinct nodes u and v in a Tree?
(किसी ट्री के किन्हीं दो अलग-अलग नोड्स u और v के बीच कितने अद्वितीय सरल पथ (simple paths) होते हैं?)
(A) 2
(B) 0
(C) Exactly 1
(D) Depends on tree degree
Correct Answer: (C)
[EN] Being connected guarantees at least one path, and being acyclic forbids alternate routes—leaving strictly 1 unique path.
[HI] ट्री जुड़ा हुआ (connected) व चक्र-रहित (acyclic) होता है, अतः किन्हीं भी दो नोड्स के बीच ठीक 1 ही रास्ता होता है।
Q8. For node D whose parent is B, whose parent is A (root), what is the set of strict Ancestors of D?
(यदि D का पैरेंट B है और B का पैरेंट रूट A है, तो D के सभी पूर्वज (Ancestors) कौन से हैं?)
(A) {A, B}
(B) {A, B, C}
(C) {E}
(D) {B} only
Correct Answer: (A)
[EN] Ancestors of D include all nodes along the upward path from D to Root: B (parent) and A (grandparent/root).
[HI] D से रूट तक जाने वाले मार्ग में पड़ने वाले सभी ऊपरी नोड्स B और A ही D के पूर्वज (Ancestors) हैं।
Q9. In any rooted tree, how many parents does every non-root node possess?
(किसी रूटेड ट्री में रूट को छोड़कर प्रत्येक अन्य नोड के कितने पैरेंट्स (Parents) होते हैं?)
(A) At least 2 parents
(B) 0 or 1 parent
(C) Unlimited parents
(D) Exactly 1 parent
Correct Answer: (D)
[EN] If a node had 2 parents, the underlying graph would contain an undirected cycle, violating the definition of a tree.
[HI] प्रत्येक गैर-रूट नोड का ठीक 1 ही पैरेंट होता है; एक से अधिक पैरेंट होने पर चक्र (cycle) बन जाएगा जो ट्री नहीं रहेगा।
Q10. What happens if you add ONE extra edge between any two non-adjacent nodes in a tree?
(यदि किसी ट्री के किन्हीं दो पहले से न जुड़े नोड्स के बीच 1 अतिरिक्त एज जोड़ दी जाए, तो क्या होगा?)
(A) It reduces total edges to V - 2
(B) It creates exactly one cycle, destroying the Tree property
(C) It creates a second Root node
(D) It turns the tree into a Forest
Correct Answer: (B)
[EN] A tree is maximally acyclic: adding even one edge between existing vertices inevitably forms a cycle.
[HI] ट्री में एक भी अतिरिक्त एज जोड़ते ही तुरंत एक चक्र (cycle) बन जाता है और वह ट्री नहीं रह जाता।
Q11. Which node in a non-empty rooted tree has zero Ancestors (strict) and zero incoming edges?
(किसी गैर-खाली ट्री में किस नोड का कोई पूर्वज (Parent) और कोई इनकमिंग एज नहीं होती?)
(A) The Root node
(B) Only Internal nodes at level 1
(C) Every Leaf node
(D) The rightmost child
Correct Answer: (A)
[EN] Only the unique Root sits at the apex with no parent above it.
[HI] केवल शीर्ष पर स्थित Root नोड ही ऐसा होता है जिसका कोई पैरेंट या पूर्वज नहीं होता।
Q12. In the example tree (Root A -> children B, C; B -> D, E; C -> F), how many Internal nodes exist?
(दिए गए ट्री (A -> B, C; B -> D, E; C -> F) में कुल कितने आंतरिक (Internal) नोड्स हैं?)
(A) 6
(B) 2 (B and C)
(C) 3 (A, B, and C)
(D) 3 (D, E, and F)
Correct Answer: (C)
[EN] Nodes A, B, and C each have at least one child (Internal), whereas D, E, and F have 0 children (Leaves).
[HI] A, B, और C के कम से कम एक बच्चा है इसलिए 3 आंतरिक नोड्स हैं, जबकि D, E, F लीफ नोड्स हैं।
Q13. Which real-world computing structure is natively organized as a rooted Tree?
(निम्नलिखित में से कौन सी वास्तविक कंप्यूटर संरचना मूलतः एक रूटेड ट्री के रूप में होती है?)
(A) Fully Meshed Peer-to-Peer Ring
(B) LIFO Undo Buffer
(C) Round-Robin CPU Ready Queue
(D) Operating System Directory / File Hierarchy & HTML DOM
Correct Answer: (D)
[EN] Directories branch hierarchically from root `/` (or `C:\`) and HTML elements nest inside `<html>` root DOM node.
[HI] ऑपरेटिंग सिस्टम का डायरेक्टरी/फाइल सिस्टम और वेब पेज का HTML DOM संरचनात्मक रूप से ट्री के उदाहरण हैं।
Q14. What differentiates a General Tree from a Graph in Data Structures?
(डेटा संरचना में एक सामान्य ट्री (Tree) और ग्राफ (Graph) में मुख्य भेद क्या है?)
(A) A Graph has V - 1 edges always
(B) A Tree cannot contain cycles and has a unique Root/hierarchy, whereas a Graph may have cycles and disconnected components
(C) A Tree can have cycles while a Graph cannot
(D) A Tree cannot use pointers
Correct Answer: (B)
[EN] Every tree is a connected acyclic graph, whereas general graphs impose no acyclicity or hierarchy constraints.
[HI] प्रत्येक ट्री एक बिना चक्र वाला जुड़ा हुआ ग्राफ है, जबकि सामान्य ग्राफ में चक्र (cycles) व कई असंबंधित भाग हो सकते हैं।
Q15. If a Forest consists of k disjoint trees and has V total vertices across all trees, how many total edges E does the Forest contain?
(यदि किसी Forest में k अलग-अलग ट्री और कुल V नोड्स हैं, तो उस Forest में कुल कितनी एजेस E होंगी?)
(A) E = V - k
(B) E = V * k
(C) E = V - 1
(D) E = V + k
Correct Answer: (A)
[EN] Each tree i with v_i nodes contributes v_i - 1 edges; summing over k trees yields sum(v_i - 1) = V - k.
[HI] प्रत्येक ट्री v_i - 1 एजेस देता है; सभी k ट्रीज को जोड़ने पर कुल एजेस V - k प्राप्त होती हैं।
Q16. Which statement is NOT true about Tree terminology?
(ट्री शब्दावली के बारे में निम्नलिखित में से कौन सा कथन असत्य (NOT true) है?)
(A) Deleting the root of a tree creates a Forest
(B) A node with zero children is called a Leaf or External node
(C) Any two nodes located at the same depth from the root are always called Siblings
(D) A tree with V nodes always has V - 1 edges
Correct Answer: (C)
[EN] Same depth alone makes nodes Cousins if their parents differ; Siblings strictly require sharing the same immediate parent.
[HI] केवल रूट से समान गहराई पर स्थित होने से दो नोड्स Siblings नहीं बनते—उनका पैरेंट भी एक ही होना अनिवार्य है।
Q17. Within Tree Terminology: Root, Node, Parent, Child, Siblings, Leaf, which tree term directly maps to: "Unique topmost node having zero parents"?
(Tree Terminology: Root, Node, Parent, Child, Siblings, Leaf में कौन सा Tree Term सीधे "Unique topmost node having zero parents" से संबंधित है?)
(A) Internal Node
(B) Root Node
(C) Siblings
(D) Leaf (External) Node
Correct Answer: (B)
[EN] In Tree Terminology: Root, Node, Parent, Child, Siblings, Leaf, 'Root Node' handles 'Unique topmost node having zero parents' (Every non-empty tree has exactly one root).
[HI] Tree Terminology: Root, Node, Parent, Child, Siblings, Leaf में 'Root Node' का कार्य/विवरण 'Unique topmost node having zero parents' (Every non-empty tree has exactly one root) है।
Q18. Which option accurately describes 'Leaf (External) Node' in Tree Terminology: Root, Node, Parent, Child, Siblings, Leaf?
(Tree Terminology: Root, Node, Parent, Child, Siblings, Leaf के संदर्भ में 'Leaf (External) Node' की सही विशेषता कौन सी है?)
(A) Two or more nodes sharing the exact same parent
(B) Node possessing at least one child node
(C) Unique topmost node having zero parents
(D) Node having zero children (out-degree = 0)
Correct Answer: (D)
[EN] 'Leaf (External) Node' provides 'Node having zero children (out-degree = 0)' — key point: Single-node tree's root is also a leaf.
[HI] 'Leaf (External) Node' का मुख्य विवरण 'Node having zero children (out-degree = 0)' है (Single-node tree's root is also a leaf)।
Q19. In Tree Terminology: Root, Node, Parent, Child, Siblings, Leaf, identify the correct parameter for the specification: "Two or more nodes sharing the exact same parent".
(Tree Terminology: Root, Node, Parent, Child, Siblings, Leaf में "Two or more nodes sharing the exact same parent" विवरण किस विकल्प के लिए सही है?)
(A) Root Node
(B) Leaf (External) Node
(C) Internal Node
(D) Siblings
Correct Answer: (D)
[EN] 'Siblings' corresponds to 'Two or more nodes sharing the exact same parent' (Same level with different parents are NOT siblings).
[HI] 'Siblings' का संबंध 'Two or more nodes sharing the exact same parent' (Same level with different parents are NOT siblings) से है।
Q20. Considering Tree Terminology: Root, Node, Parent, Child, Siblings, Leaf, what key behavior defines 'Internal Node'?
(Tree Terminology: Root, Node, Parent, Child, Siblings, Leaf में 'Internal Node' की मुख्य भूमिका या मान क्या है?)
(A) Unique topmost node having zero parents
(B) Node possessing at least one child node
(C) Two or more nodes sharing the exact same parent
(D) Node having zero children (out-degree = 0)
Correct Answer: (B)
[EN] 'Internal Node' represents 'Node possessing at least one child node' (Root is internal whenever tree size > 1).
[HI] 'Internal Node' का अर्थ/मान 'Node possessing at least one child node' है (Root is internal whenever tree size > 1)।
Tree Terminology: Root, Node, Parent, Child, Siblings, Leaf — Exam FAQs
Q1: Can an empty structure with 0 nodes be called a Tree?
क्या 0 नोड्स वाली खाली संरचना को भी ट्री कहा जा सकता है?
[EN] Yes, in computer science algorithms (like BSTs and Binary Trees), an Empty Tree (NULL root, 0 nodes) is valid as a base case, whereas in pure graph theory a tree is often defined as having at least 1 vertex.
[HI] हाँ, कंप्यूटर विज्ञान (BST, बाइनरी ट्री) में NULL रूट वाले 0-नोड ट्री को Empty Tree माना जाता है, जबकि शुद्ध ग्राफ सिद्धांत में कम से कम 1 नोड जरूरी माना जाता है।
Q2: Is the Root node considered an Internal node?
क्या रूट नोड को आंतरिक (Internal) नोड माना जाता है?
[EN] Yes, whenever the tree has 2 or more nodes (so the root has at least 1 child). Only in a 1-node tree where the root has 0 children is the root classified as a Leaf.
[HI] हाँ, जब भी ट्री में 2 या अधिक नोड्स हों तो रूट का कम से कम 1 बच्चा होता है और वह Internal नोड कहलाता है; केवल 1-नोड ट्री में रूट को Leaf माना जाता है।
Q3: What is the difference between a Subtree and a Forest?
सबट्री (Subtree) और फॉरेस्ट (Forest) में क्या अंतर है?
[EN] A Subtree is a single tree formed by picking one node and all its descendants. A Forest is a collection of zero or more mutually disjoint trees (for example, all subtrees left behind after deleting the root).
[HI] Subtree किसी एक नोड और उसके सभी वंशजों से बना एक अकेला ट्री होता है, जबकि Forest कई अलग-अलग असंबद्ध ट्रीज का समूह होता है।
Post a Comment
Post a Comment