PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम Strict / Full Binary Tree: Definition and Internal/Leaf Relation (पूर्ण (Full / Strict) बाइनरी ट्री: 0 या 2 बच्चे और पत्ती नोड्स संबंध) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।
Overview: A Strict Binary Tree (also called Full or Proper Binary Tree / 2-Tree) restricts every node to having either 0 or 2 children, strictly forbidding degree-1 nodes (n1 = 0). Consequently, leaves always satisfy L = I + 1 relative to internal nodes I, total node count N = 2I + 1 is strictly odd, and height-h strict trees contain between 2h + 1 and 2^(h+1) - 1 nodes.
अध्याय सार: पूर्ण या स्ट्रिक्ट बाइनरी ट्री (Strict / Full / Proper Binary Tree) में प्रत्येक नोड के या तो ठीक 0 बच्चे होते हैं या ठीक 2 बच्चे—अर्थात 1 बच्चे वाला कोई नोड (n1 = 0) नहीं हो सकता। इससे पत्तियाँ L = I + 1 नियम का पालन करती हैं, कुल नोड्स N = 2I + 1 हमेशा विषम (Odd) रहते हैं, और h ऊंचाई पर न्यूनतम 2h + 1 व अधिकतम 2^(h+1) - 1 नोड्स होते हैं।
Strict / Full Binary Tree: Definition and Internal/Leaf Relation: Detailed Notes & Architecture (पूर्ण (Full / Strict) बाइनरी ट्री: 0 या 2 बच्चे और पत्ती नोड्स संबंध)
1. Definition (0 or 2 Children) and Full vs Perfect vs Complete Contrast (परिभाषा (0 या 2 बच्चे) और Full बनाम Perfect बनाम Complete भेद)
[EN] In a Strict (Full / Proper) Binary Tree, every node has out-degree 0 (Leaf) or out-degree 2 (Internal), meaning n1 = 0 always. Exam terminology carefully distinguishes three standard types: a Full/Strict Binary Tree requires only 0 or 2 children per node (leaves may reside at different depths); a Perfect Binary Tree requires every internal node to have 2 children AND every leaf to lie at the exact same depth (2^(h+1) - 1 nodes); a Complete Binary Tree has all levels fully packed except possibly the last level filled strictly left-to-right.
[HI] स्ट्रिक्ट (Full / Proper) बाइनरी ट्री में हर नोड की डिग्री केवल 0 या 2 हो सकती है, अर्थात किसी नोड का अकेला बच्चा (n1) नहीं होता। परीक्षा की तीन प्रमुख शब्दावलियों का अंतर स्पष्ट समझें: Full/Strict में सभी पत्तियाँ एक ही गहराई पर होना जरूरी नहीं; Perfect बाइनरी ट्री में सभी पत्तियाँ समान गहराई पर होती हैं (2^(h+1)-1 नोड्स); और Complete बाइनरी ट्री में अंतिम स्तर बाईं से दाईं ओर क्रम से भरा होता है।
2. Internal-to-Leaf Node Relation (L = I + 1) and Always-Odd Proof (आंतरिक व पत्ती नोड संबंध (L = I + 1) और हमेशा-विषम नियम)
[EN] Because n1 = 0, every non-leaf internal node has exactly 2 children (so I = n2) and leaves are L = n0. Total nodes equal N = I + L, while total outgoing edges from internal nodes equal 2I. Since every tree satisfies Edges = N - 1, setting 2I = I + L - 1 proves L = I + 1. Substituting back gives N = 2I + 1 = 2L - 1, proving that a Strict/Full Binary Tree MUST always have an ODD total number of nodes (never 2, 4, 6, 8, ...).
[HI] चूंकि n1 = 0 है, सभी आंतरिक नोड्स (I) के 2 बच्चे होते हैं, अतः ट्री की कुल एजेस 2I होती हैं। दूसरी ओर, कुल एजेस हमेशा N - 1 = (I + L) - 1 होती हैं। दोनों को बराबर रखने पर 2I = I + L - 1 से L = I + 1 सिद्ध होता है। इस प्रकार कुल नोड्स N = I + L = 2I + 1 = 2L - 1 प्राप्त होता है, जो यह साबित करता है कि स्ट्रिक्ट बाइनरी ट्री में नोड्स की कुल संख्या हमेशा विषम (Odd) होती है।
3. Node and Height Extremes (2h + 1 Minimum and (N - 1)/2 Max Height) (न्यूनतम/अधिकतम नोड्स व ऊंचाई सीमाएं (2h + 1 और (N - 1)/2))
[EN] Given edge-based height h, the MINIMUM nodes required to construct a Strict Binary Tree equal 2h + 1 (achieved as a zigzag spine adding 1 internal node and 1 leaf at each level down from root), while MAXIMUM nodes equal 2^(h+1) - 1 (Perfect Binary Tree). Conversely, for a fixed odd node count N, minimum height is floor(log2(N)) and maximum height is (N - 1) / 2—half the skewed general binary tree bound N - 1! Expressing I and L directly from N yields I = (N - 1) / 2 and L = (N + 1) / 2.
[HI] एज-आधारित ऊंचाई h पर स्ट्रिक्ट बाइनरी ट्री बनाने के लिए न्यूनतम 2h + 1 नोड्स (हर स्तर पर एक जोड़ी जोड़ते हुए) तथा अधिकतम 2^(h+1) - 1 नोड्स लगते हैं। विषम कुल नोड्स N ज्ञात होने पर न्यूनतम ऊंचाई floor(log2(N)) और अधिकतम ऊंचाई (N - 1)/2 होती है—जो सामान्य बाइनरी ट्री के N - 1 से ठीक आधी है! N से सीधे सूत्र: I = (N - 1)/2 और L = (N + 1)/2।
4. Real Applications: Expression Trees, Huffman Coding, and Decision Trees (वास्तविक अनुप्रयोग: एक्सप्रेशन ट्री, हफमैन कोडिंग और डिसीजन ट्री)
[EN] Binary Expression Trees parsing arithmetic operators (+, -, *, /) naturally form Strict Binary Trees: every binary operator is an internal node with exactly 2 operand subtrees, while every numeric literal or variable is a leaf node. Similarly, Huffman Optimal Prefix Coding merges the two smallest frequency nodes at every step, producing a Strict Binary Tree whose leaves store all source symbols. Binary Decision Trees and knockout tournament brackets also strictly maintain 0 or 2 children per node.
[HI] अंकगणितीय एक्सप्रेशन ट्री में प्रत्येक बाइनरी ऑपरेटर (+, -, *, /) दो ऑपरेंड के साथ आंतरिक नोड बनता है और मान/चर लीफ बनते हैं—अतः यह स्वाभाविक रूप से स्ट्रिक्ट बाइनरी ट्री होता है। इसी तरह हफमैन कोडिंग ट्री और बाइनरी डिसीजन ट्री भी हमेशा 0 या 2 बच्चों के नियम का पालन करते हैं।
Syntax, Formula & Technical Example (Strict / Full Binary Tree: Definition and Internal/Leaf Relation)
// Recursive C validator for Strict / Full Binary Tree:
int isStrictBinary(struct BNode *root) {
if (root == NULL) return 1;
if (root->left == NULL && root->right == NULL) return 1;
if (root->left != NULL && root->right != NULL)
return isStrictBinary(root->left) && isStrictBinary(root->right);
return 0; // Node has exactly 1 child -> NOT strict!
}
// Identities: L = I + 1 | N = 2I + 1 (Always Odd) | Min nodes(h) = 2h + 1
Strict / Full Binary Tree: Definition and Internal/Leaf Relation Quick Reference & Comparison Table
| Strict Binary Tree Property | Exact Mathematical Formula | Key Exam Fact |
|---|---|---|
| Allowed Node Degree | Strictly 0 or 2 children per node (n1 = 0) | Single-child nodes strictly forbidden |
| Leaf vs Internal Nodes | L = I + 1 (leaves exceed internals by 1) | From 2I = I + L - 1 edge count |
| Total Nodes Parity | N = 2I + 1 = 2L - 1 (always odd) | Even total node counts are impossible |
| Min Nodes at Height h | 2h + 1 nodes (max height for N is (N-1)/2) | Occurs in caterpillar strict tree |
Strict / Full Binary Tree: Definition and Internal/Leaf Relation Top 20 Bilingual MCQs with Answers
Q1. What condition strictly defines a Strict (Full / Proper) Binary Tree?
(स्ट्रिक्ट (Full / Proper) बाइनरी ट्री की सटीक परिभाषा क्या है?)
(A) Every internal node has at most 1 child
(B) Every leaf node must lie at the same depth
(C) Every node has either 0 children or exactly 2 children (no degree-1 nodes)
(D) Every node has exactly 2 children including leaves
Correct Answer: (C)
[EN] In a Strict/Full Binary Tree, n1 = 0: every node is either a leaf (0 children) or an internal node with both left and right children (2 children).
[HI] स्ट्रिक्ट बाइनरी ट्री में कोई भी 1-बच्चे वाला नोड (n1) नहीं हो सकता; हर नोड के 0 या 2 ही बच्चे होते हैं।
Q2. If a Strict Binary Tree contains 18 Internal nodes (I = 18), how many Leaf nodes (L) and Total nodes (N) does it have?
(यदि किसी स्ट्रिक्ट बाइनरी ट्री में 18 आंतरिक नोड्स (I = 18) हैं, तो उसमें कुल पत्ती नोड्स (L) और कुल नोड्स (N) कितने होंगे?)
(A) L = 17 leaves, N = 35 total nodes
(B) L = 20 leaves, N = 38 total nodes
(C) L = 18 leaves, N = 36 total nodes
(D) L = 19 leaves, N = 37 total nodes
Correct Answer: (D)
[EN] Using L = I + 1 gives 18 + 1 = 19 leaves, and N = I + L = 18 + 19 = 37 total nodes.
[HI] सूत्र L = I + 1 से 19 पत्तियाँ और कुल नोड्स N = 18 + 19 = 37 प्राप्त होते हैं।
Q3. Which total node count CANNOT belong to ANY valid non-empty Strict Binary Tree?
(निम्नलिखित में से किस संख्या के नोड्स वाला कोई भी गैर-खाली स्ट्रिक्ट बाइनरी ट्री बनाना असंभव है?)
(A) 7
(B) 16
(C) 1
(D) 25
Correct Answer: (B)
[EN] Since N = 2I + 1, every non-empty Strict Binary Tree must have an ODD number of nodes; an even count like 16 is impossible.
[HI] N = 2I + 1 होने के कारण स्ट्रिक्ट बाइनरी ट्री में नोड्स हमेशा विषम (Odd) होते हैं; अतः सम संख्या 16 असंभव है।
Q4. If a Strict Binary Tree has N = 45 total nodes, how many Internal nodes (I) and Leaf nodes (L) exist?
(यदि किसी स्ट्रिक्ट बाइनरी ट्री में कुल 45 नोड्स हैं, तो उसमें आंतरिक नोड्स (I) और पत्तियाँ (L) क्रमशः कितनी होंगी?)
(A) I = 23 internal nodes and L = 22 leaves
(B) I = 21 internal nodes and L = 24 leaves
(C) Cannot be determined without height
(D) I = 22 internal nodes and L = 23 leaves
Correct Answer: (D)
[EN] I = (N - 1) / 2 = 44 / 2 = 22, and L = (N + 1) / 2 = 46 / 2 = 23.
[HI] I = (45 - 1)/2 = 22 आंतरिक नोड्स और L = (45 + 1)/2 = 23 पत्ती नोड्स होंगे।
Q5. What is the MINIMUM number of nodes in a Strict Binary Tree of edge-based height h = 6?
(एज-आधारित ऊंचाई h = 6 वाले स्ट्रिक्ट बाइनरी ट्री में न्यूनतम कितने नोड्स हो सकते हैं?)
(A) 64
(B) 13
(C) 127
(D) 7
Correct Answer: (B)
[EN] Minimum nodes = 2h + 1 = 2(6) + 1 = 13 (1 root + 2 children at each of the 6 downward levels).
[HI] न्यूनतम नोड्स का सूत्र 2h + 1 = 2(6) + 1 = 13 होता है।
Q6. What is the MAXIMUM possible edge-based height of a Strict Binary Tree built from N = 21 nodes?
(21 नोड्स से बने स्ट्रिक्ट बाइनरी ट्री की अधिकतम संभावित एज-आधारित ऊंचाई क्या हो सकती है?)
(A) 11
(B) 4
(C) 10
(D) 20
Correct Answer: (C)
[EN] Maximum height of a strict binary tree occurs at minimal branching per level: h_max = (N - 1) / 2 = (21 - 1) / 2 = 10.
[HI] स्ट्रिक्ट बाइनरी ट्री की अधिकतम ऊंचाई (N - 1)/2 = (21 - 1)/2 = 10 होती है (सामान्य बाइनरी ट्री के 20 से आधी)।
Q7. How does a Strict (Full) Binary Tree differ from a Perfect Binary Tree?
(स्ट्रिक्ट (Full) बाइनरी ट्री और परफेक्ट (Perfect) बाइनरी ट्री में मुख्य अंतर क्या है?)
(A) Strict allows leaves at different depths as long as every node has 0 or 2 children; Perfect additionally requires all leaves at the same depth
(B) Strict allows 1-child nodes; Perfect forbids them
(C) Perfect allows even total node counts; Strict does not
(D) Strict must always have 2^(h+1) - 1 nodes
Correct Answer: (A)
[EN] Every Perfect Binary Tree is Strict, but a Strict Binary Tree need not be symmetric or have equal-depth leaves.
[HI] हर परफेक्ट बाइनरी ट्री स्ट्रिक्ट होता है, पर स्ट्रिक्ट ट्री में सभी पत्तियों का एक ही गहराई पर होना आवश्यक नहीं है।
Q8. Suppose a Strict Binary Tree has 100 Leaf nodes. How many total nodes does it have?
(यदि किसी स्ट्रिक्ट बाइनरी ट्री में 100 पत्ती (Leaf) नोड्स हैं, तो उसमें कुल कितने नोड्स होंगे?)
(A) 200
(B) 101
(C) 199
(D) 201
Correct Answer: (C)
[EN] Since I = L - 1 = 99, total nodes N = I + L = 99 + 100 = 199 (equivalently N = 2L - 1).
[HI] N = 2L - 1 = 2(100) - 1 = 199 कुल नोड्स होंगे।
Q9. Which practical tree structure is guaranteed to be a Strict Binary Tree whenever constructed for binary arithmetic expressions like (a + b) * (c - d)?
(अंकगणितीय अभिव्यक्तियों जैसे (a + b) * (c - d) को दर्शाने वाला कौन सा ट्री हमेशा एक स्ट्रिक्ट बाइनरी ट्री होता है?)
(A) Threaded Binary Search Tree
(B) B+ Tree with degree 5
(C) Skewed Left-Chain List
(D) Binary Expression Tree (binary operators as internal nodes, operands as leaves)
Correct Answer: (D)
[EN] Every binary operator node has strictly 2 operand subtrees (left and right), while numbers/variables have 0 children.
[HI] बाइनरी एक्सप्रेशन ट्री में प्रत्येक ऑपरेटर के ठीक 2 बच्चे और प्रत्येक ऑपरेंड के 0 बच्चे होते हैं, जिससे वह सदैव स्ट्रिक्ट रहता है।
Q10. Is a single-node binary tree (just the Root with left=NULL and right=NULL) considered a valid Strict Binary Tree?
(क्या केवल 1 नोड वाला ट्री (जहाँ रूट के बायां व दायां दोनों NULL हैं) एक वैध स्ट्रिक्ट बाइनरी ट्री माना जाता है?)
(A) Only if height >= 1
(B) No — a strict binary tree must have at least 3 nodes
(C) No — root must always have 2 children
(D) Yes — its lone node has 0 children (and I = 0, L = 1 satisfies L = I + 1)
Correct Answer: (D)
[EN] The lone root has degree 0 (which is in {0, 2}), satisfying `L = I + 1` (1 = 0 + 1) and odd count N = 1.
[HI] हाँ! अकेले रूट के 0 बच्चे हैं (जो 0 या 2 के नियम को पूरा करता है) तथा N = 1 विषम संख्या और L = I + 1 भी सत्य है।
Q11. In a Strict Binary Tree, what is the number of nodes with degree 1 (n1)?
(स्ट्रिक्ट बाइनरी ट्री में ठीक 1 बच्चे वाले नोड्स (n1) की संख्या कितनी होती है?)
(A) At most 1 at the last level
(B) N / 2
(C) Equal to height h
(D) Always 0
Correct Answer: (D)
[EN] Forbidding single-child nodes is the defining constraint of a Strict/Full Binary Tree (n1 = 0).
[HI] स्ट्रिक्ट बाइनरी ट्री की परिभाषा ही यही है कि किसी भी नोड का केवल 1 बच्चा नहीं होगा (n1 = 0)।
Q12. In the recursive C function `isStrictBinary(root)`, what happens when `root->left != NULL` and `root->right == NULL`?
(रिकर्सिव C फंक्शन `isStrictBinary(root)` में यदि `root->left != NULL` और `root->right == NULL` मिले, तो वह क्या लौटाएगा?)
(A) Recurses down root->left only
(B) Returns 1 (true)
(C) Swaps left and right children
(D) Returns 0 (false), because that node has exactly 1 child
Correct Answer: (D)
[EN] Having one non-NULL child and one NULL child violates the 0-or-2 rule, immediately returning 0 (false).
[HI] एक बच्चा होने और दूसरा NULL होने से 0 या 2 बच्चों की शर्त टूटती है, इसलिए फंक्शन तुरंत 0 (असत्य) लौटाता है।
Q13. How many edges are present in a Strict Binary Tree containing I internal nodes?
(I आंतरिक नोड्स वाले एक स्ट्रिक्ट बाइनरी ट्री में कुल कितनी एजेस (Edges) होती हैं?)
(A) I - 1
(B) 2 * I
(C) I + 1
(D) 2 * I + 1
Correct Answer: (B)
[EN] Each of the I internal nodes contributes exactly 2 downward child edges, and leaves contribute 0, giving 2I edges (matching N - 1 = (2I + 1) - 1 = 2I).
[HI] प्रत्येक आंतरिक नोड से ठीक 2 एजेस निकलती हैं और पत्तियों से 0, इसलिए कुल एजेस 2 * I होती हैं।
Q14. Does a Complete Binary Tree (like a Binary Heap with 6 elements) always qualify as a Strict Binary Tree?
(क्या 6 तत्वों वाला एक Complete Binary Tree (जैसे बाइनरी हीप) हमेशा एक Strict Binary Tree होता है?)
(A) Yes — because heaps forbid 1-child nodes
(B) No — a Complete Binary Tree with an even count like 6 elements MUST contain one node with exactly 1 child
(C) Yes — every Complete Binary Tree is Strict
(D) Only when N = 2^k
Correct Answer: (B)
[EN] With 6 elements in a heap, node at index 2 (0-based) has only a left child at index 5 (degree 1), making it Complete yet NOT Strict!
[HI] नहीं! 6 तत्वों वाले हीप में एक नोड का केवल बायां बच्चा (1 बच्चा) होगा और कुल नोड्स सम (6) हैं, अतः वह Complete तो है पर Strict नहीं।
Q15. What happens if you construct a Huffman Coding Tree for an alphabet of 12 distinct characters?
(12 अलग-अलग अक्षरों की वर्णमाला के लिए Huffman कोडिंग ट्री बनाने पर उसमें कुल कितने आंतरिक नोड्स और कुल नोड्स होंगे?)
(A) 11 internal merge nodes and 23 total nodes (since Huffman trees are Strict Binary Trees)
(B) 12 internal nodes and 24 total nodes
(C) 12 internal nodes and 23 total nodes
(D) 6 internal nodes and 18 total nodes
Correct Answer: (A)
[EN] The 12 characters sit at the 12 leaves (L = 12); Huffman merges pairs repeatedly, forming a Strict Binary Tree with I = L - 1 = 11 internal nodes and N = 23 total nodes.
[HI] 12 अक्षर 12 पत्तियां बनते हैं (L=12); हफमैन मर्जिंग से बना स्ट्रिक्ट ट्री I = 12 - 1 = 11 आंतरिक नोड्स व कुल 23 नोड्स रखता है।
Q16. Which statement is NOT true about Strict / Full Binary Trees?
(स्ट्रिक्ट / फुल बाइनरी ट्री के बारे में इनमें से कौन सा कथन असत्य (NOT true) है?)
(A) Number of leaf nodes equals internal nodes plus 1 (L = I + 1)
(B) Total number of nodes in a non-empty strict binary tree is always odd
(C) Every Strict Binary Tree of height h must contain exactly 2^(h + 1) - 1 nodes
(D) Every internal node has exactly 2 children
Correct Answer: (C)
[EN] 2^(h + 1) - 1 is the MAXIMUM (Perfect Binary Tree), whereas a Strict Binary Tree of height h can have as few as 2h + 1 nodes.
[HI] ऊंचाई h पर 2^(h + 1) - 1 नोड्स अधिकतम सीमा (Perfect ट्री) हैं; स्ट्रिक्ट ट्री में न्यूनतम 2h + 1 नोड्स भी हो सकते हैं।
Q17. Within Strict / Full Binary Tree: Definition and Internal/Leaf Relation, which strict binary tree property directly maps to: "Strictly 0 or 2 children per node (n1 = 0)"?
(Strict / Full Binary Tree: Definition and Internal/Leaf Relation में कौन सा Strict Binary Tree Property सीधे "Strictly 0 or 2 children per node (n1 = 0)" से संबंधित है?)
(A) Min Nodes at Height h
(B) Allowed Node Degree
(C) Leaf vs Internal Nodes
(D) Total Nodes Parity
Correct Answer: (B)
[EN] In Strict / Full Binary Tree: Definition and Internal/Leaf Relation, 'Allowed Node Degree' handles 'Strictly 0 or 2 children per node (n1 = 0)' (Single-child nodes strictly forbidden).
[HI] Strict / Full Binary Tree: Definition and Internal/Leaf Relation में 'Allowed Node Degree' का कार्य/विवरण 'Strictly 0 or 2 children per node (n1 = 0)' (Single-child nodes strictly forbidden) है।
Q18. Which option accurately describes 'Leaf vs Internal Nodes' in Strict / Full Binary Tree: Definition and Internal/Leaf Relation?
(Strict / Full Binary Tree: Definition and Internal/Leaf Relation के संदर्भ में 'Leaf vs Internal Nodes' की सही विशेषता कौन सी है?)
(A) L = I + 1 (leaves exceed internals by 1)
(B) N = 2I + 1 = 2L - 1 (always odd)
(C) Strictly 0 or 2 children per node (n1 = 0)
(D) 2h + 1 nodes (max height for N is (N-1)/2)
Correct Answer: (A)
[EN] 'Leaf vs Internal Nodes' provides 'L = I + 1 (leaves exceed internals by 1)' — key point: From 2I = I + L - 1 edge count.
[HI] 'Leaf vs Internal Nodes' का मुख्य विवरण 'L = I + 1 (leaves exceed internals by 1)' है (From 2I = I + L - 1 edge count)।
Q19. In Strict / Full Binary Tree: Definition and Internal/Leaf Relation, identify the correct parameter for the specification: "N = 2I + 1 = 2L - 1 (always odd)".
(Strict / Full Binary Tree: Definition and Internal/Leaf Relation में "N = 2I + 1 = 2L - 1 (always odd)" विवरण किस विकल्प के लिए सही है?)
(A) Min Nodes at Height h
(B) Leaf vs Internal Nodes
(C) Total Nodes Parity
(D) Allowed Node Degree
Correct Answer: (C)
[EN] 'Total Nodes Parity' corresponds to 'N = 2I + 1 = 2L - 1 (always odd)' (Even total node counts are impossible).
[HI] 'Total Nodes Parity' का संबंध 'N = 2I + 1 = 2L - 1 (always odd)' (Even total node counts are impossible) से है।
Q20. Considering Strict / Full Binary Tree: Definition and Internal/Leaf Relation, what key behavior defines 'Min Nodes at Height h'?
(Strict / Full Binary Tree: Definition and Internal/Leaf Relation में 'Min Nodes at Height h' की मुख्य भूमिका या मान क्या है?)
(A) 2h + 1 nodes (max height for N is (N-1)/2)
(B) L = I + 1 (leaves exceed internals by 1)
(C) N = 2I + 1 = 2L - 1 (always odd)
(D) Strictly 0 or 2 children per node (n1 = 0)
Correct Answer: (A)
[EN] 'Min Nodes at Height h' represents '2h + 1 nodes (max height for N is (N-1)/2)' (Occurs in caterpillar strict tree).
[HI] 'Min Nodes at Height h' का अर्थ/मान '2h + 1 nodes (max height for N is (N-1)/2)' है (Occurs in caterpillar strict tree)।
Strict / Full Binary Tree: Definition and Internal/Leaf Relation — Exam FAQs
Q1: Why do some textbooks confuse 'Full Binary Tree' with 'Complete Binary Tree' or 'Perfect Binary Tree'?
कुछ किताबों में 'Full Binary Tree', 'Complete Binary Tree' और 'Perfect Binary Tree' के नाम आपस में उलझे हुए क्यों मिलते हैं?
[EN] Older textbooks (like Horowitz/Lipschutz) sometimes called a Perfect tree 'Full' and a 0/2-child tree 'Strict' or 'Extended 2-Tree', whereas modern CLRS / GATE terminology uses 'Full Binary Tree' synonymously with 'Strict/Proper Binary Tree' (0 or 2 children) and 'Perfect Binary Tree' when all levels are completely filled.
[HI] पुरानी किताबों में कहीं 'Full' का अर्थ पूरी तरह भरा ट्री लिख दिया जाता था, जबकि आधुनिक मानक (CLRS/GATE) में Full या Strict का अर्थ '0 या 2 बच्चे' और पूरी तरह भरे ट्री को 'Perfect Binary Tree' कहा जाता है।
Q2: How do you remember the difference between L = I + 1 and n0 = n2 + 1?
L = I + 1 और n0 = n2 + 1 सूत्रों के बीच का संबंध आसानी से कैसे याद रखें?
[EN] They are the exact same theorem! In a general binary tree, n0 = n2 + 1 regardless of n1; in a Strict Binary Tree, n1 = 0, so ALL non-leaf internal nodes belong to n2 (I = n2) and leaves are n0 (L = n0), directly giving L = I + 1.
[HI] दोनों एक ही प्रमेय हैं! सामान्य बाइनरी ट्री में n0 = n2 + 1 हमेशा सत्य है; चूंकि स्ट्रिक्ट बाइनरी ट्री में n1 = 0 होता है, इसलिए सभी आंतरिक नोड्स I = n2 हो जाते हैं और L = I + 1 बनता है।
Q3: Can a Strict Binary Tree ever have an even number of edges?
क्या किसी स्ट्रिक्ट बाइनरी ट्री में एजेस (Edges) की संख्या हमेशा सम (Even) होती है?
[EN] Yes! Because total nodes N = 2I + 1 is always odd, total edges E = N - 1 = 2I is always even (0, 2, 4, 6, ...).
[HI] हाँ! क्योंकि कुल नोड्स N = 2I + 1 हमेशा विषम होते हैं, इसलिए एजेस E = N - 1 = 2I हमेशा सम (Even) संख्या में होती हैं।
Post a Comment
Post a Comment