PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम Tree Properties: Degree, Level, Depth, Height of Node/Tree (ट्री गुण: डिग्री, लेवल, गहराई (Depth) और ट्री की ऊंचाई (Height)) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।
Overview: Tree properties quantify branching and vertical span through Degree (children count of a node; maximum node degree across the tree), Level, Depth (edges downward from Root, with Depth(Root) = 0), and Height (edges along longest downward path to a Leaf, with Height(Leaf) = 0). Knowing both edge-based (Depth(Root)=0) and node-based (Level(Root)=1) conventions eliminates exam ambiguity.
अध्याय सार: ट्री के गुण उसकी शाखाओं और ऊर्ध्वाधर विस्तार को मापते हैं: Degree (किसी नोड के बच्चों की संख्या; पूरे ट्री की अधिकतम डिग्री), Level, Depth (रूट से नीचे नोड तक एजेस, Root की Depth = 0), और Height (नोड से सबसे दूर पत्ती तक एजेस, Leaf की Height = 0)। एज-आधारित व नोड-आधारित दोनों नियमों की स्पष्ट समझ परीक्षा के भ्रम समाप्त करती है।
Tree Properties: Degree, Level, Depth, Height of Node/Tree: Detailed Notes & Architecture (ट्री गुण: डिग्री, लेवल, गहराई (Depth) और ट्री की ऊंचाई (Height))
1. Degree of a Node vs Degree of a Tree (नोड की डिग्री बनाम ट्री की डिग्री)
[EN] The Degree of a specific node equals its total number of direct children (subtrees); thus every Leaf node has degree 0. Crucially, the Degree of a Tree is NOT the sum of node degrees—it is defined as the MAXIMUM degree possessed by any single node in that tree. For instance, if a tree's nodes have 0, 1, 2, or 3 children, the tree has degree 3 (ternary tree), while a Binary Tree always has tree degree <= 2.
[HI] किसी एक नोड के सीधे बच्चों (Subtrees) की संख्या को उस नोड की डिग्री कहते हैं, इसलिए हर Leaf की डिग्री 0 होती है। पूरे ट्री की डिग्री सभी डिग्रियों का योग नहीं, बल्कि ट्री के किसी भी नोड की अधिकतम डिग्री होती है। उदाहरणार्थ, यदि एक नोड के अधिकतम 3 बच्चे हैं तो वह डिग्री-3 का ट्री होगा, और बाइनरी ट्री की डिग्री हमेशा 2 से अधिक नहीं हो सकती।
2. Depth of a Node (Top-Down) and Level Indexing (नोड की गहराई (Depth) और स्तर (Level) नियम)
[EN] The Depth of a node X is measured top-down as the number of edges along the unique path from the Root down to X. Under the standard edge-based convention (CLRS / GATE), the Root has Depth = 0, its immediate children have Depth = 1, and so forth. While many texts define Level == Depth (Root at Level 0), some classical Indian textbooks index Level starting at 1 (Root at Level 1, children at Level 2), so Level(X) = Depth(X) + 1 in 1-based exams.
[HI] किसी नोड X की Depth (गहराई) ऊपर से नीचे रूट से X तक आने वाले मार्ग की एजेस गिनकर निकाली जाती है। मानक एज-आधारित नियम में Root की Depth = 0 और उसके बच्चों की Depth = 1 होती है। कई आधुनिक पुस्तकों में Level और Depth समान (Root = Level 0) होते हैं, जबकि कुछ पारंपरिक भारतीय पुस्तकों में Root को Level 1 माना जाता है (जहाँ Level = Depth + 1)।
3. Height of a Node vs Height of a Tree (Bottom-Up) (नोड की ऊंचाई (Height) और पूरे ट्री की ऊंचाई)
[EN] The Height of a node X is measured bottom-up as the number of edges on the longest downward simple path from X to any descendant Leaf. Therefore, every Leaf node has Height = 0, and the Height of a Tree equals the Height of its Root—which numerically equals the maximum Depth among all nodes in the tree! Notice that Depth(X) + Height(X) <= Height(Tree), with equality holding exclusively for nodes lying along a longest root-to-leaf path.
[HI] किसी नोड X की Height (ऊंचाई) नीचे से ऊपर की ओर X से उसकी सबसे दूरस्थ पत्ती (Leaf) तक के सबसे लंबे पथ की एजेस से मापी जाती है। अतः प्रत्येक Leaf नोड की Height = 0 होती है और पूरे ट्री की ऊंचाई उसके Root की Height (अथवा ट्री की अधिकतम Depth) के बराबर होती है। किसी नोड X के लिए Depth(X) + Height(X) <= Height(Tree) होता है।
4. Edge-Based vs Node-Based Empty and Single-Node Base Cases (एज-आधारित बनाम नोड-आधारित खाली व एक-नोड सीमांत नियम)
[EN] Under edge-based height (standard in C/C++/GATE recursion: return -1 for NULL, else 1 + max(left, right)), a single-node tree has Height = 0 and an empty tree (NULL) has Height = -1. Under node-based height (counting vertices on longest path, used in older RSMSSB/Lipschutz questions), an empty tree has Height = 0 and a single-node tree has Height = 1. Knowing both ensures you never lose marks regardless of which convention an exam specifies.
[HI] एज-आधारित ऊंचाई (C रिकर्शन में NULL पर -1 लौटाना) में एक अकेले रूट वाले ट्री की Height = 0 और खाली ट्री की Height = -1 होती है। वहीं नोड-आधारित नियम (पथ के नोड्स गिनना) में खाली ट्री की Height = 0 और 1-नोड ट्री की Height = 1 मानी जाती है। परीक्षा में दिए गए आधार के अनुसार सही मान चुनना चाहिए।
Syntax, Formula & Technical Example (Tree Properties: Degree, Level, Depth, Height of Node/Tree)
// Edge-based Height in C (Empty = -1, Single Leaf = 0):
int height(struct Node *root) {
if (root == NULL) return -1;
int lh = height(root->left);
int rh = height(root->right);
return 1 + (lh > rh ? lh : rh);
}
// Example: A -> (B, C) -> B has child D
// Depth(A)=0, Depth(C)=1, Depth(D)=2 | Height(D)=0, Height(C)=0, Height(B)=1, Height(A)=2
Tree Properties: Degree, Level, Depth, Height of Node/Tree Quick Reference & Comparison Table
| Tree Property | Edge-Based Standard Definition | Key Exam Fact |
|---|---|---|
| Degree of a Node | Count of direct children attached below the node | Always 0 for every Leaf node |
| Degree of a Tree | Maximum node degree present anywhere in the tree | Binary tree max degree is 2 |
| Depth of Node X | Edges from Root downward to X (Root = 0) | Top-down distance from Root |
| Height of Node X | Edges on longest path from X down to a Leaf (Leaf = 0) | Height(Tree) = Height(Root) = max Depth |
Tree Properties: Degree, Level, Depth, Height of Node/Tree Top 20 Bilingual MCQs with Answers
Q1. How is the 'Degree of a Tree' formally defined?
(किसी ट्री की 'डिग्री (Degree of a Tree)' को किस प्रकार परिभाषित किया जाता है?)
(A) The height of the root node
(B) The sum of degrees of all nodes
(C) The total number of leaf nodes
(D) The maximum degree among all individual nodes in the tree
Correct Answer: (D)
[EN] Tree degree represents the branching upper bound—equal to the largest child count owned by any node in the tree.
[HI] पूरे ट्री के सभी नोड्स में से जिस नोड के सबसे अधिक बच्चे हों, वही संख्या पूरे ट्री की डिग्री कहलाती है।
Q2. What is the Degree of every Leaf (External) node in a tree?
(ट्री के प्रत्येक Leaf (पत्ती) नोड की डिग्री कितनी होती है?)
(A) Equal to tree height
(B) 1
(C) -1
(D) 0
Correct Answer: (D)
[EN] Because a leaf node has zero children, its degree is strictly 0.
[HI] चूंकि लीफ नोड का कोई बच्चा नहीं होता, इसलिए उसकी डिग्री हमेशा 0 होती है।
Q3. Under standard edge-based definitions (CLRS/GATE), what are Depth(Root) and Height(Leaf) respectively?
(मानक एज-आधारित परिभाषा के अनुसार क्रमशः Depth(Root) और Height(Leaf) के मान क्या होते हैं?)
(A) Depth(Root) = 1 and Height(Leaf) = 1
(B) Depth(Root) = 0 and Height(Leaf) = 0
(C) Depth(Root) = 0 and Height(Leaf) = -1
(D) Depth(Root) = -1 and Height(Leaf) = 0
Correct Answer: (B)
[EN] There are 0 edges from Root to Root (Depth=0) and 0 edges from a Leaf to itself (Height=0).
[HI] रूट से रूट तक 0 एजेस (Depth=0) और पत्ती से पत्ती तक 0 एजेस (Height=0) होती हैं।
Q4. If a tree contains Root A with children B and C, and B has child D (so D is the deepest node), what are Depth(B) and Height(B) (edge-based)?
(यदि ट्री में रूट A के बच्चे B व C हैं, और B का बच्चा D है, तो एज-आधारित विधि में Depth(B) और Height(B) क्रमशः कितने होंगे?)
(A) Depth(B) = 0, Height(B) = 2
(B) Depth(B) = 2, Height(B) = 1
(C) Depth(B) = 1, Height(B) = 1
(D) Depth(B) = 1, Height(B) = 0
Correct Answer: (C)
[EN] B is 1 edge below Root A (Depth=1) and 1 edge above Leaf D (Height=1).
[HI] B रूट A से 1 एज नीचे है (Depth=1) और अपनी पत्ती D से 1 एज ऊपर है (Height=1)।
Q5. In that same tree (A -> B, C; B -> D), what are Depth(C) and Height(C) (edge-based)?
(उसी ट्री (A -> B, C; B -> D) में नोड C की Depth और Height (एज-आधारित) क्रमशः क्या होंगी?)
(A) Depth(C) = 1, Height(C) = 0
(B) Depth(C) = 1, Height(C) = 1
(C) Depth(C) = 2, Height(C) = 0
(D) Depth(C) = 0, Height(C) = 1
Correct Answer: (A)
[EN] C sits 1 edge from Root A (Depth=1), yet C itself is a Leaf with no children (Height=0). Note Depth(C)+Height(C)=1 < Tree Height 2!
[HI] C रूट से 1 एज नीचे (Depth=1) है, पर स्वयं एक पत्ती होने के कारण उसकी Height = 0 है।
Q6. In recursive C code `int height(Node* r)`, what base-case return value yields edge-based height (0 for a single-node tree)?
(रिकर्सिव C फंक्शन `int height(Node* r)` में खाली (NULL) होने पर कौन सा मान लौटाने से एक-नोड ट्री की ऊंचाई 0 मिलती है?)
(A) 0
(B) 1
(C) INT_MIN
(D) -1
Correct Answer: (D)
[EN] When r is a single leaf node, `1 + max(-1, -1)` yields `1 + (-1) = 0`!
[HI] NULL पर -1 लौटाने से एक अकेले नोड के लिए `1 + max(-1, -1) = 0` सटीक एज-आधारित ऊंचाई मिलती है।
Q7. If an exam uses node-based height (counting vertices on the longest path from root to leaf), what is the height of an empty tree vs a single-node tree?
(यदि परीक्षा में नोड-आधारित ऊंचाई (पथ के नोड्स की गिनती) प्रयुक्त हो, तो खाली ट्री और 1-नोड ट्री की ऊंचाई क्रमशः क्या होगी?)
(A) Empty tree: 0, Single-node tree: 0
(B) Empty tree: -1, Single-node tree: 0
(C) Empty tree: 1, Single-node tree: 2
(D) Empty tree: 0, Single-node tree: 1
Correct Answer: (D)
[EN] Counting nodes along the longest path yields 0 vertices when empty and 1 vertex for a lone root.
[HI] पथ पर नोड्स गिनने वाली विधि में खाली ट्री में 0 नोड्स (Height=0) और 1-नोड ट्री में 1 नोड (Height=1) होता है।
Q8. For any tree, which equality ALWAYS holds true (edge-based)?
(किसी भी ट्री के लिए निम्नलिखित में से कौन सा समीकरण हमेशा सत्य होता है?)
(A) Height(Root) == Sum of all node heights
(B) Height of the Tree == Height of the Root == Maximum Depth among all leaves
(C) Depth(X) == Height(X) for every node X
(D) Degree of Tree == Height of Tree
Correct Answer: (B)
[EN] The longest downward path from Root to a leaf equals the deepest leaf's distance from Root.
[HI] रूट से सबसे दूर पत्ती तक की लंबाई (Height of Root) ही ट्री की अधिकतम गहराई (max Depth) व ट्री की ऊंचाई होती है।
Q9. Suppose Root is defined at Level 1 (1-based level convention). If a node sits at Depth 4 (4 edges below Root), what Level is it at?
(यदि रूट को Level 1 माना जाए, तो रूट से 4 एजेस नीचे (Depth = 4) स्थित नोड किस Level पर होगा?)
(A) Level 6
(B) Level 5
(C) Level 3
(D) Level 4
Correct Answer: (B)
[EN] Under 1-based levels, Level = Depth + 1 = 4 + 1 = 5.
[HI] जब रूट Level 1 पर हो, तो Level = Depth + 1 = 4 + 1 = 5 होगा।
Q10. Which inequality accurately relates Depth(x), Height(x), and TreeHeight for an arbitrary node x in a tree?
(किसी भी नोड x के लिए Depth(x), Height(x) और TreeHeight के बीच सही संबंध क्या है?)
(A) Depth(x) + Height(x) >= TreeHeight
(B) Depth(x) + Height(x) <= TreeHeight
(C) Depth(x) + Height(x) == TreeHeight always
(D) Depth(x) * Height(x) == TreeHeight
Correct Answer: (B)
[EN] Equality holds only if x sits along a maximum-length root-to-leaf path; nodes in shorter branches satisfy `< TreeHeight`.
[HI] केवल सबसे लंबे रूट-टू-लीफ पथ वाले नोड्स के लिए योग TreeHeight के बराबर होता है, अन्य के लिए <= TreeHeight रहता है।
Q11. A tree has nodes A, B, C, D, E, F where A has 3 children (B, C, D), B has 2 children (E, F), and C, D, E, F are leaves. What is the Degree of the Tree?
(एक ट्री में A के 3 बच्चे (B, C, D) और B के 2 बच्चे (E, F) हैं तथा C, D, E, F पत्तियाँ हैं। इस ट्री की डिग्री कितनी होगी?)
(A) 3
(B) 2
(C) 6
(D) 5
Correct Answer: (A)
[EN] Node degrees are A=3, B=2, C=D=E=F=0; maximum node degree is 3.
[HI] नोड्स की डिग्रियां A=3, B=2 और बाकी 0 हैं; अधिकतम मान 3 होने से ट्री की डिग्री 3 होगी।
Q12. How do you compute the Height of an entire tree when only node Depth values are given?
(यदि ट्री के सभी नोड्स की केवल Depth ज्ञात हो, तो पूरे ट्री की Height (एज-आधारित) कैसे निकलेगी?)
(A) Average all node Depth values
(B) Take the minimum non-zero Depth
(C) Sum all leaf Depth values
(D) Take the maximum Depth value among all nodes in the tree
Correct Answer: (D)
[EN] Every node's depth measures its edge distance from root, so the greatest depth equals the longest root-to-leaf path (Tree Height).
[HI] ट्री में किसी भी नोड की अधिकतम Depth ही रूट से सबसे दूर पत्ती तक की लंबाई अर्थात ट्री की Height होती है।
Q13. In a strictly linear chain tree of 7 nodes (A -> B -> C -> D -> E -> F -> G), what are Tree Degree and Edge-Based Tree Height?
(7 नोड्स वाले एक सीधी श्रृंखला जैसे ट्री (A->B->C->D->E->F->G) की डिग्री और एज-आधारित ऊंचाई क्रमशः क्या होंगी?)
(A) Tree Degree = 1, Tree Height = 7
(B) Tree Degree = 2, Tree Height = 6
(C) Tree Degree = 7, Tree Height = 7
(D) Tree Degree = 1, Tree Height = 6
Correct Answer: (D)
[EN] Each non-leaf node has 1 child (Degree=1), and 7 vertices in a chain are linked by 6 edges (Height=6).
[HI] प्रत्येक आंतरिक नोड का केवल 1 बच्चा है (डिग्री=1) और 7 नोड्स के बीच 6 एजेस होने से ऊंचाई 6 होगी।
Q14. Which metric is strictly determined 'bottom-up' from descendant leaves toward a node?
(निम्नलिखित में से कौन सा माप किसी नोड के नीचे स्थित पत्तियों से ऊपर की ओर (Bottom-Up) मापा जाता है?)
(A) Level of the node
(B) In-degree of the node
(C) Height of the node
(D) Depth of the node
Correct Answer: (C)
[EN] Height depends on the subtrees below a node (distance to deepest leaf), whereas Depth depends on the path above from Root.
[HI] ऊंचाई (Height) हमेशा नोड के नीचे की सबसे दूरस्थ पत्ती से तय होती है, जबकि गहराई (Depth) ऊपर रूट से गिनी जाती है।
Q15. If a Binary Search Tree of 31 nodes is completely balanced, what is its edge-based Height?
(यदि 31 नोड्स वाला एक बाइनरी सर्च ट्री पूर्णतः संतुलित (Completely Balanced) हो, तो उसकी एज-आधारित ऊंचाई कितनी होगी?)
(A) 30
(B) 5
(C) 4
(D) 31
Correct Answer: (C)
[EN] With height h = 4 (levels 0,1,2,3,4), max nodes = 2^(4+1) - 1 = 31.
[HI] ऊंचाई 4 (कुल 5 स्तर: 0 से 4) में 1 + 2 + 4 + 8 + 16 = 31 नोड्स पूर्णतः संतुलित रूप से आते हैं।
Q16. Which statement is NOT true regarding Tree properties?
(ट्री के गुणों के संबंध में निम्नलिखित में से कौन सा कथन असत्य (NOT true) है?)
(A) Degree of a leaf node is always 0
(B) Every node in a tree always has identical Height and Depth values
(C) Depth is measured downward from the Root node
(D) Degree of a tree equals the maximum degree among its nodes
Correct Answer: (B)
[EN] A leaf at bottom has Depth = h and Height = 0, while Root has Depth = 0 and Height = h—they differ on almost every node.
[HI] प्रत्येक नोड की Height और Depth बराबर नहीं होती; जैसे रूट पर Depth=0 व Height=h और सबसे निचली पत्ती पर Depth=h व Height=0 होती है।
Q17. Within Tree Properties: Degree, Level, Depth, Height of Node/Tree, which tree property directly maps to: "Count of direct children attached below the node"?
(Tree Properties: Degree, Level, Depth, Height of Node/Tree में कौन सा Tree Property सीधे "Count of direct children attached below the node" से संबंधित है?)
(A) Degree of a Node
(B) Height of Node X
(C) Depth of Node X
(D) Degree of a Tree
Correct Answer: (A)
[EN] In Tree Properties: Degree, Level, Depth, Height of Node/Tree, 'Degree of a Node' handles 'Count of direct children attached below the node' (Always 0 for every Leaf node).
[HI] Tree Properties: Degree, Level, Depth, Height of Node/Tree में 'Degree of a Node' का कार्य/विवरण 'Count of direct children attached below the node' (Always 0 for every Leaf node) है।
Q18. Which option accurately describes 'Degree of a Tree' in Tree Properties: Degree, Level, Depth, Height of Node/Tree?
(Tree Properties: Degree, Level, Depth, Height of Node/Tree के संदर्भ में 'Degree of a Tree' की सही विशेषता कौन सी है?)
(A) Count of direct children attached below the node
(B) Maximum node degree present anywhere in the tree
(C) Edges on longest path from X down to a Leaf (Leaf = 0)
(D) Edges from Root downward to X (Root = 0)
Correct Answer: (B)
[EN] 'Degree of a Tree' provides 'Maximum node degree present anywhere in the tree' — key point: Binary tree max degree is 2.
[HI] 'Degree of a Tree' का मुख्य विवरण 'Maximum node degree present anywhere in the tree' है (Binary tree max degree is 2)।
Q19. In Tree Properties: Degree, Level, Depth, Height of Node/Tree, identify the correct parameter for the specification: "Edges from Root downward to X (Root = 0)".
(Tree Properties: Degree, Level, Depth, Height of Node/Tree में "Edges from Root downward to X (Root = 0)" विवरण किस विकल्प के लिए सही है?)
(A) Height of Node X
(B) Degree of a Node
(C) Degree of a Tree
(D) Depth of Node X
Correct Answer: (D)
[EN] 'Depth of Node X' corresponds to 'Edges from Root downward to X (Root = 0)' (Top-down distance from Root).
[HI] 'Depth of Node X' का संबंध 'Edges from Root downward to X (Root = 0)' (Top-down distance from Root) से है।
Q20. Considering Tree Properties: Degree, Level, Depth, Height of Node/Tree, what key behavior defines 'Height of Node X'?
(Tree Properties: Degree, Level, Depth, Height of Node/Tree में 'Height of Node X' की मुख्य भूमिका या मान क्या है?)
(A) Edges on longest path from X down to a Leaf (Leaf = 0)
(B) Edges from Root downward to X (Root = 0)
(C) Maximum node degree present anywhere in the tree
(D) Count of direct children attached below the node
Correct Answer: (A)
[EN] 'Height of Node X' represents 'Edges on longest path from X down to a Leaf (Leaf = 0)' (Height(Tree) = Height(Root) = max Depth).
[HI] 'Height of Node X' का अर्थ/मान 'Edges on longest path from X down to a Leaf (Leaf = 0)' है (Height(Tree) = Height(Root) = max Depth)।
Tree Properties: Degree, Level, Depth, Height of Node/Tree — Exam FAQs
Q1: Why do some exam questions say a 3-level tree has height 2 while others say height 3?
कुछ परीक्षाओं में 3 स्तर वाले ट्री की ऊंचाई 2 और कुछ में 3 क्यों बताई जाती है?
[EN] Edge-based height (modern CLRS/GATE standard) counts edges, so 3 levels (0, 1, 2) give height = 2. Node-based height (older textbooks) counts vertices on the longest path, giving height = 3. Always check whether the question indexes root at Level 0 (edge-based) or Level 1 (node-based).
[HI] एज-आधारित ऊंचाई में एजेस गिनी जाती हैं इसलिए 3 स्तरों (0, 1, 2) पर ऊंचाई 2 होती है। नोड-आधारित ऊंचाई में पथ के नोड्स गिने जाते हैं जिससे 3 मिलती है।
Q2: Are 'Depth of a Tree' and 'Height of a Tree' the same value?
क्या 'ट्री की गहराई (Depth of Tree)' और 'ट्री की ऊंचाई (Height of Tree)' समान होती हैं?
[EN] Yes, at the whole-tree level: Height of the tree (= height of root) equals Maximum Depth among all nodes in the tree. However, for an individual internal node X, Depth(X) and Height(X) are generally completely different numbers!
[HI] हाँ, पूरे ट्री के लिए दोनों बराबर होती हैं (ट्री की ऊंचाई = ट्री की अधिकतम गहराई)। लेकिन किसी एक नोड X के लिए उसकी Depth और Height प्रायः अलग-अलग होती हैं।
Q3: Can the Degree of a Binary Tree ever be 1 or 0?
क्या किसी बाइनरी ट्री की डिग्री 1 या 0 भी हो सकती है?
[EN] Yes! A Binary Tree permits AT MOST 2 children per node. A single-node binary tree has degree 0, a skewed chain binary tree has degree 1, and any binary tree with at least one 2-child node has degree 2.
[HI] हाँ! बाइनरी ट्री का नियम 'अधिकतम 2 बच्चे' है—अतः 1-नोड ट्री की डिग्री 0 और सीधी श्रृंखला की डिग्री 1 हो सकती है।
Post a Comment
Post a Comment