PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम Level Order Traversal (BFS) of Binary Tree using Queue (लेवल ऑर्डर ट्रैवर्सल: कतार आधारित ब्रेड्थ-फर्स्ट सर्च (BFS)) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।
Overview: Level Order Traversal executes Breadth-First Search (BFS) on a binary tree by visiting nodes level by level from top to bottom and left to right using a FIFO Queue. It runs in O(n) time and O(w) auxiliary space—where w is maximum tree width (reaching ceil(n/2) in Complete trees versus O(1) in Skewed trees)—making it ideal for shortest-path discovery and level-based views.
अध्याय सार: लेवल ऑर्डर ट्रैवर्सल बाइनरी ट्री पर ब्रेड्थ-फर्स्ट सर्च (BFS) लागू करता है, जिसमें FIFO कतार (Queue) का उपयोग कर नोड्स को ऊपर से नीचे प्रत्येक स्तर पर बाएं से दाएं विज़िट किया जाता है। इसकी समय जटिलता O(n) तथा स्पेस जटिलता O(w) (ट्री की अधिकतम चौड़ाई, जो पूर्ण ट्री में लगभग n/2 होती है) होती है।
Level Order Traversal (BFS) of Binary Tree using Queue: Detailed Notes & Architecture (लेवल ऑर्डर ट्रैवर्सल: कतार आधारित ब्रेड्थ-फर्स्ट सर्च (BFS))
1. FIFO Queue Mechanism & Level-by-Level BFS Execution (FIFO कतार (Queue) कार्यप्रणाली व BFS निष्पादन)
[EN] Unlike DFS traversals that rely on a LIFO stack or recursion, Level Order Traversal uses a First-In-First-Out (FIFO) Queue. Starting by enqueuing `root`, each iteration dequeues the front node `curr`, processes `curr->data`, enqueues `curr->left` (if non-NULL), and then enqueues `curr->right` (if non-NULL). Because nodes added at depth d sit ahead of all nodes pushed for depth d+1, every level completes strictly from left to right before advancing downward.
[HI] DFS के विपरीत, लेवल ऑर्डर ट्रैवर्सल में First-In-First-Out (FIFO) कतार (Queue) उपयोग की जाती है। प्रारंभ में रूट को कतार में डाला जाता है; फिर लूप में आगे से नोड निकालकर (Dequeue) प्रोसेस करते हैं और यदि लेफ्ट व राइट चाइल्ड मौजूद हों तो उन्हें क्रमशः कतार के पीछे (Enqueue) जोड़ते जाते हैं। इससे गहराई d के सभी नोड्स d+1 से पहले पूरे हो जाते हैं।
2. Level-Wise Grouping with Inner Size Loop (लेवल-वार समूहीकरण (Inner Size Loop तकनीक))
[EN] Standard BFS prints a flat stream of all nodes, whereas capturing `levelSize = queueSize()` at the beginning of each outer `while` iteration lets an inner `for` loop drain exactly one depth level at a time. This minor refinement unlocks tree width calculation, level averages, Left/Right Side Views, Zigzag (Spiral) traversal via a deque or alternating flag, and Reverse Level Order (by pushing popped items onto a stack).
[HI] प्रत्येक बाहरी लूप के आरंभ में `levelSize = queue.size()` नोट करके एक आंतरिक `for` लूप चलाने से हर स्तर के नोड्स अलग-अलग बैच में मिल जाते हैं। इसी तकनीक से ट्री की अधिकतम चौड़ाई (Width), लेफ्ट/राइट व्यू, प्रत्येक स्तर का औसत तथा ज़िग-ज़ैग (Zigzag/Spiral) ट्रैवर्सल आसानी से निकाले जाते हैं।
3. Time & Width-Driven Space Complexity Analysis (समय व चौड़ाई-आधारित स्पेस जटिलता विश्लेषण)
[EN] Every node enters and leaves the queue exactly once, fixing time complexity at Theta(n). Crucially, BFS space complexity is O(w), where w is the maximum number of nodes at any single level—the exact opposite pattern of DFS! In a Skewed tree (w = 1), BFS uses only O(1) space while DFS consumes O(n) stack space; conversely, in a Perfect or Complete Binary Tree, the bottom level holds ceil(n/2) nodes, forcing BFS queue space up to Theta(n) while DFS stays at O(log n).
[HI] प्रत्येक नोड कतार में एक बार प्रवेश और एक बार निकास करता है, अतः समय जटिलता Theta(n) होती है। परंतु स्पेस जटिलता ट्री की अधिकतम चौड़ाई O(w) पर निर्भर करती है: स्क्यूड ट्री (w=1) में BFS केवल O(1) स्पेस लेता है जबकि परफेक्ट/कम्प्लीट ट्री में अंतिम स्तर पर लगभग n/2 नोड्स होने से कतार का आकार O(n) तक पहुंच जाता है।
4. Practical Applications: Shortest Path, CBT Check & Serialization (व्यावहारिक अनुप्रयोग: न्यूनतम पथ, CBT जांच व सीरियलाइजेशन)
[EN] Because BFS explores nodes in strictly non-decreasing order of edge distance from the root, the very first leaf node encountered during Level Order Traversal guarantees the minimum tree depth (shortest root-to-leaf path). BFS also verifies Complete Binary Tree integrity (checking that no non-NULL node follows a NULL child) and powers standard array/heap serialization formats used in competitive programming and database indexes.
[HI] चूंकि BFS रूट से दूरी (Edges) के बढ़ते क्रम में आगे बढ़ता है, इसलिए लेवल ऑर्डर में मिलने वाली पहली पत्ती (Leaf) ट्री की न्यूनतम गहराई (Shortest Root-to-Leaf Path) दर्शाती है। इसका उपयोग यह जांचने के लिए भी होता है कि कोई ट्री कम्प्लीट बाइनरी ट्री (CBT) है या नहीं।
Syntax, Formula & Technical Example (Level Order Traversal (BFS) of Binary Tree using Queue)
// Level Order Traversal (BFS) with Level-by-Level Grouping
void levelOrder(Node* root) {
if (!root) return;
Queue q; enqueue(&q, root);
while (!isEmpty(&q)) {
int levelSize = size(&q);
for (int i = 0; i < levelSize; i++) {
Node* curr = dequeue(&q);
printf("%d ", curr->data);
if (curr->left) enqueue(&q, curr->left);
if (curr->right) enqueue(&q, curr->right);
}
}
}
Level Order Traversal (BFS) of Binary Tree using Queue Quick Reference & Comparison Table
| BFS / Level Order Factor | Specification / Bound | Exam Comparison |
|---|---|---|
| Core Data Structure | FIFO Queue (enqueue rear, dequeue front) | Contrast with LIFO Stack used in DFS |
| Worst-Case Queue Space | O(n) — specifically ceil(n/2) on CBT/Perfect | Occurs at deepest wide level of balanced trees |
| Skewed Tree Queue Space | O(1) — holds at most 1 node at a time | More space-efficient than O(n) DFS on skewed trees |
| Minimum Depth Discovery | First leaf encountered gives min height | Guaranteed because levels are visited top-down |
Level Order Traversal (BFS) of Binary Tree using Queue Top 20 Bilingual MCQs with Answers
Q1. Which data structure is primarily used to implement Level Order Traversal (BFS) of a binary tree?
(बाइनरी ट्री के लेवल ऑर्डर ट्रैवर्सल (BFS) को लागू करने के लिए मुख्यतः किस डेटा संरचना का उपयोग होता है?)
(A) Priority Heap
(B) Stack (LIFO)
(C) Circular Doubly Linked List
(D) Queue (FIFO)
Correct Answer: (D)
[EN] Level Order processes nodes level-by-level in order of discovery, requiring First-In-First-Out (FIFO) Queue behavior.
[HI] नोड्स को उनके मिलने के क्रम (स्तर-दर-स्तर) में प्रोसेस करने के लिए FIFO कतार (Queue) अनिवार्य है।
Q2. Given Root = 10, Left = 20 (Left=40, Right=50), Right = 30 (Right=60), what is the Level Order output?
(यदि रूट 10 हो, लेफ्ट 20 (चाइल्ड 40, 50) तथा राइट 30 (राइट चाइल्ड 60) हो, तो लेवल ऑर्डर ट्रैवर्सल क्या होगा?)
(A) 10, 20, 30, 40, 50, 60
(B) 40, 20, 50, 10, 30, 60
(C) 10, 20, 40, 50, 30, 60
(D) 40, 50, 60, 20, 30, 10
Correct Answer: (A)
[EN] Level 0: [10], Level 1: [20, 30], Level 2: [40, 50, 60], giving 10, 20, 30, 40, 50, 60.
[HI] स्तर 0 पर 10, स्तर 1 पर 20 व 30, तथा स्तर 2 पर 40, 50 व 60 विज़िट होंगे।
Q3. What is the worst-case auxiliary space complexity of Queue-based Level Order Traversal on an n-node Complete Binary Tree?
(n नोड्स वाले कम्प्लीट बाइनरी ट्री पर कतार आधारित लेवल ऑर्डर ट्रैवर्सल की सबसे खराब स्थिति में स्पेस जटिलता क्या है?)
(A) O(n) — holding up to ceil(n/2) nodes in the queue
(B) O(log n)
(C) O(1)
(D) O(n log n)
Correct Answer: (A)
[EN] The bottom level of a Complete/Perfect Binary Tree holds about n/2 nodes simultaneously inside the queue, which is Theta(n).
[HI] कम्प्लीट या परफेक्ट बाइनरी ट्री के अंतिम स्तर पर लगभग n/2 नोड्स एक साथ कतार में आ जाते हैं, जो O(n) है।
Q4. How much auxiliary queue space does Level Order Traversal require on a strictly Right-Skewed binary tree of n = 1000 nodes?
(n = 1000 नोड्स वाले पूरी तरह राइट-स्क्यूड बाइनरी ट्री पर लेवल ऑर्डर ट्रैवर्सल को कतार में अधिकतम कितना स्थान चाहिए?)
(A) O(n/2) — 500 nodes
(B) O(n) — 1000 nodes
(C) O(log n)
(D) O(1) — maximum queue size is 1
Correct Answer: (D)
[EN] Each level of a skewed tree contains only 1 node, so dequeueing 1 node and enqueueing 1 child keeps queue size <= 1.
[HI] स्क्यूड ट्री के प्रत्येक स्तर पर केवल 1 नोड होता है, इसलिए कतार का अधिकतम आकार 1 अर्थात O(1) रहता है।
Q5. In a Perfect Binary Tree with n = 31 nodes, what is the maximum number of nodes present in the Queue at one time during BFS?
(n = 31 नोड्स वाले परफेक्ट बाइनरी ट्री में BFS के दौरान कतार में एक समय पर अधिकतम कितने नोड्स रहेंगे?)
(A) 5
(B) 15
(C) 31
(D) 16
Correct Answer: (D)
[EN] A Perfect Binary Tree of 31 nodes (h=4) has 2^4 = 16 leaves on its last level; all 16 sit in the queue together.
[HI] 31 नोड्स वाले परफेक्ट ट्री के सबसे निचले स्तर पर (31+1)/2 = 16 पत्तियां होती हैं जो एक साथ कतार में होंगी।
Q6. To compute the Right Side View of a binary tree using Level Order Traversal, which node from each level is selected?
(लेवल ऑर्डर ट्रैवर्सल से बाइनरी ट्री का 'राइट साइड व्यू' निकालने के लिए प्रत्येक स्तर से कौन सा नोड चुना जाता है?)
(A) The first node processed at each level
(B) The last node processed at each level (index levelSize - 1)
(C) Only nodes at odd levels
(D) Only nodes with no left child
Correct Answer: (B)
[EN] When visiting left-to-right per level, the rightmost visible node is always the final element of that level's queue batch.
[HI] बाएं से दाएं विज़िट करते समय हर स्तर का सबसे अंतिम (Rightmost) नोड ही दाईं ओर से दिखाई देता है।
Q7. Which traversal visits nodes in exact increasing order of their distance (number of edges) from the root?
(कौन सा ट्रैवर्सल नोड्स को रूट से उनकी दूरी (Edges की संख्या) के बढ़ते क्रम में विज़िट करता है?)
(A) Postorder Traversal (DFS)
(B) Inorder Traversal (DFS)
(C) Level Order Traversal (BFS)
(D) Preorder Traversal (DFS)
Correct Answer: (C)
[EN] Depth 0 is visited before depth 1, depth 1 before depth 2, matching shortest-hop BFS ordering.
[HI] गहराई 0, फिर 1, फिर 2 के क्रम में चलने के कारण BFS रूट से दूरी के बढ़ते क्रम में नोड्स देखता है।
Q8. How is Reverse Level Order Traversal (bottom level to top level, left-to-right at each level) typically implemented?
(रिवर्स लेवल ऑर्डर ट्रैवर्सल (नीचे से ऊपर, प्रत्येक स्तर पर बाएं से दाएं) को सामान्यतः कैसे लागू किया जाता है?)
(A) Run Preorder and reverse the result
(B) Use a Stack instead of a Queue directly
(C) Enqueue left child before right child and use a Heap
(D) Enqueue right child before left child in a Queue, and push each dequeued node onto a Stack
Correct Answer: (D)
[EN] Pushing right-then-left into BFS queue puts level-order reversed per level; popping from the Stack prints bottom-to-top, left-to-right!
[HI] कतार में पहले राइट फिर लेफ्ट चाइल्ड डालकर निकले हुए नोड्स को स्टैक में रखने पर स्टैक से नीचे से ऊपर सही क्रम निकलता है।
Q9. How does Zigzag (Spiral) Level Order Traversal differ from standard Level Order Traversal?
(ज़िग-ज़ैग (स्पाइरल) लेवल ऑर्डर ट्रैवर्सल सामान्य लेवल ऑर्डर से किस प्रकार भिन्न है?)
(A) It alternates traversal direction at every level (left-to-right, then right-to-left)
(B) It visits leaves before internal nodes
(C) It skips every odd-numbered level
(D) It always visits the right subtree first at every level
Correct Answer: (A)
[EN] Even levels proceed left-to-right and odd levels right-to-left using a Deque or Two Stacks.
[HI] ज़िग-ज़ैग में एक स्तर बाएं से दाएं और अगला स्तर दाएं से बाएं (दिशा बदलते हुए) विज़िट किया जाता है।
Q10. If a Queue overflows or memory is severely restricted on a massive balanced binary tree (n = 10^8), why might DFS beat BFS?
(एक विशाल संतुलित बाइनरी ट्री (n = 10^8) पर मेमोरी सीमित होने पर DFS को BFS पर वरीयता क्यों दी जा सकती है?)
(A) DFS runs faster asymptotically than O(n)
(B) DFS never uses pointers
(C) BFS fails to visit leaf nodes
(D) DFS uses only O(log n) stack space (~27 frames), whereas BFS queue needs O(n) (~50 million nodes)
Correct Answer: (D)
[EN] On balanced trees, O(log n) space is negligible compared to storing the entire O(n/2) leaf frontier in a BFS queue.
[HI] संतुलित ट्री में DFS को केवल O(log n) स्टैक स्थान चाहिए, जबकि BFS की कतार में अंतिम स्तर के लगभग n/2 नोड्स भर जाते हैं।
Q11. Which condition inside a Level Order traversal guarantees finding the minimum depth (shortest path to any leaf) of a binary tree?
(लेवल ऑर्डर ट्रैवर्सल के दौरान कौन सी स्थिति ट्री की न्यूनतम गहराई (Minimum Depth) को तुरंत बता देती है?)
(A) The depth of the last node dequeued
(B) The depth of the very first node encountered having both left == NULL and right == NULL
(C) Maximum queue size reached
(D) First node whose data is minimum
Correct Answer: (B)
[EN] BFS discovers levels monotonically; the first leaf reached requires no further exploration of deeper levels.
[HI] BFS चूंकि स्तर-वार आगे बढ़ता है, इसलिए सबसे पहले मिलने वाली पत्ती (दोनों चाइल्ड NULL) की गहराई ही न्यूनतम होती है।
Q12. In the level-grouped BFS loop, why must `int levelSize = size(&q);` be saved BEFORE the inner `for` loop?
(लेवल-समूहीकृत BFS में आंतरिक `for` लूप शुरू करने से पहले `levelSize = size(&q)` सहेजना क्यों जरूरी है?)
(A) Because enqueueing children inside the loop grows the queue size dynamically
(B) Because C compilers forbid calling size() in loops
(C) To sort the elements of the queue
(D) To double the speed of dequeue()
Correct Answer: (A)
[EN] If you checked `i < size(&q)` dynamically, newly pushed children from the next level would mix into the current level.
[HI] लूप के अंदर बच्चों को कतार में जोड़ने से कतार का आकार बढ़ता रहता है, इसलिए वर्तमान स्तर की सीमा तय करने को पहले साइज सहेजा जाता है।
Q13. What is the Level Order Traversal of a Binary Search Tree formed by inserting 30, 15, 45, 10, 20, 40 in that exact order?
(खाली BST में क्रमशः 30, 15, 45, 10, 20, 40 डालने से बने ट्री का लेवल ऑर्डर ट्रैवर्सल क्या होगा?)
(A) 30, 15, 10, 20, 45, 40
(B) 10, 20, 15, 40, 45, 30
(C) 30, 15, 45, 10, 20, 40
(D) 10, 15, 20, 30, 40, 45
Correct Answer: (C)
[EN] Level 0: 30; Level 1: 15, 45; Level 2: 10, 20, 40—matching the exact insertion sequence!
[HI] स्तरीय संरचना: स्तर 0 पर 30, स्तर 1 पर 15, 45 और स्तर 2 पर 10, 20, 40 (डाले गए क्रम के समान)।
Q14. Which statement is NOT true about Level Order Traversal (BFS)?
(लेवल ऑर्डर ट्रैवर्सल (BFS) के बारे में इनमें से कौन सा कथन असत्य (NOT true) है?)
(A) Level Order Traversal uses O(log n) worst-case auxiliary space on a Complete Binary Tree
(B) Level Order can detect whether a binary tree is a Complete Binary Tree
(C) Level Order visits root first before any node at depth 1
(D) Level Order Traversal visits every node in Theta(n) time
Correct Answer: (A)
[EN] On a Complete Binary Tree, queue size reaches ceil(n/2) = Theta(n), NOT O(log n)!
[HI] कम्प्लीट बाइनरी ट्री पर कतार का आकार n/2 अर्थात O(n) तक जाता है, O(log n) नहीं!
Q15. During Level Order serialization of a binary tree of n = 5 nodes stored in a Complete Binary Tree array, how many nodes are enqueued?
(यदि 5 नोड्स का कम्प्लीट बाइनरी ट्री हो और मानक लेवल ऑर्डर चलाया जाए (केवल गैर-NULL चाइल्ड पर), तो `enqueue` कुल कितनी बार चलेगा?)
(A) 5 times
(B) 10 times
(C) 4 times
(D) 6 times
Correct Answer: (A)
[EN] Root is enqueued once and every other node is enqueued once by its parent: exactly n = 5 enqueues.
[HI] रूट एक बार और बाकी हर नोड अपने पेरेंट द्वारा एक बार कतार में डाला जाता है—अतः कुल n = 5 बार।
Q16. Which problem CANNOT be solved cleanly in a single pass without storing extra depth/level info using pure recursive DFS, yet is trivial with BFS?
(इनमें से कौन सा कार्य शुद्ध BFS (Queue) में सबसे स्वाभाविक रूप से स्तर-दर-स्तर बिना एक्स्ट्रा पैरामीटर के हल होता है?)
(A) Evaluating a Postfix expression tree
(B) Printing nodes level-by-level in horizontal breadth order from top to bottom
(C) Deleting all tree nodes bottom-up
(D) Printing BST elements in sorted order
Correct Answer: (B)
[EN] BFS natively explores horizontal levels; DFS dives vertically along branches first.
[HI] BFS प्राकृतिक रूप से क्षैतिज स्तरों के अनुसार प्रिंट करता है, जबकि DFS लंबवत शाखाओं में गहराई तक जाता है।
Q17. Within Level Order Traversal (BFS) of Binary Tree using Queue, which bfs / level order factor directly maps to: "FIFO Queue (enqueue rear, dequeue front)"?
(Level Order Traversal (BFS) of Binary Tree using Queue में कौन सा BFS / Level Order Factor सीधे "FIFO Queue (enqueue rear, dequeue front)" से संबंधित है?)
(A) Core Data Structure
(B) Minimum Depth Discovery
(C) Skewed Tree Queue Space
(D) Worst-Case Queue Space
Correct Answer: (A)
[EN] In Level Order Traversal (BFS) of Binary Tree using Queue, 'Core Data Structure' handles 'FIFO Queue (enqueue rear, dequeue front)' (Contrast with LIFO Stack used in DFS).
[HI] Level Order Traversal (BFS) of Binary Tree using Queue में 'Core Data Structure' का कार्य/विवरण 'FIFO Queue (enqueue rear, dequeue front)' (Contrast with LIFO Stack used in DFS) है।
Q18. Which option accurately describes 'Worst-Case Queue Space' in Level Order Traversal (BFS) of Binary Tree using Queue?
(Level Order Traversal (BFS) of Binary Tree using Queue के संदर्भ में 'Worst-Case Queue Space' की सही विशेषता कौन सी है?)
(A) O(n) — specifically ceil(n/2) on CBT/Perfect
(B) O(1) — holds at most 1 node at a time
(C) First leaf encountered gives min height
(D) FIFO Queue (enqueue rear, dequeue front)
Correct Answer: (A)
[EN] 'Worst-Case Queue Space' provides 'O(n) — specifically ceil(n/2) on CBT/Perfect' — key point: Occurs at deepest wide level of balanced trees.
[HI] 'Worst-Case Queue Space' का मुख्य विवरण 'O(n) — specifically ceil(n/2) on CBT/Perfect' है (Occurs at deepest wide level of balanced trees)।
Q19. In Level Order Traversal (BFS) of Binary Tree using Queue, identify the correct parameter for the specification: "O(1) — holds at most 1 node at a time".
(Level Order Traversal (BFS) of Binary Tree using Queue में "O(1) — holds at most 1 node at a time" विवरण किस विकल्प के लिए सही है?)
(A) Core Data Structure
(B) Worst-Case Queue Space
(C) Skewed Tree Queue Space
(D) Minimum Depth Discovery
Correct Answer: (C)
[EN] 'Skewed Tree Queue Space' corresponds to 'O(1) — holds at most 1 node at a time' (More space-efficient than O(n) DFS on skewed trees).
[HI] 'Skewed Tree Queue Space' का संबंध 'O(1) — holds at most 1 node at a time' (More space-efficient than O(n) DFS on skewed trees) से है।
Q20. Considering Level Order Traversal (BFS) of Binary Tree using Queue, what key behavior defines 'Minimum Depth Discovery'?
(Level Order Traversal (BFS) of Binary Tree using Queue में 'Minimum Depth Discovery' की मुख्य भूमिका या मान क्या है?)
(A) O(1) — holds at most 1 node at a time
(B) O(n) — specifically ceil(n/2) on CBT/Perfect
(C) FIFO Queue (enqueue rear, dequeue front)
(D) First leaf encountered gives min height
Correct Answer: (D)
[EN] 'Minimum Depth Discovery' represents 'First leaf encountered gives min height' (Guaranteed because levels are visited top-down).
[HI] 'Minimum Depth Discovery' का अर्थ/मान 'First leaf encountered gives min height' है (Guaranteed because levels are visited top-down)।
Level Order Traversal (BFS) of Binary Tree using Queue — Exam FAQs
Q1: Can Level Order Traversal be implemented recursively without a Queue?
क्या लेवल ऑर्डर ट्रैवर्सल को बिना कतार (Queue) के रिकर्सिव तरीके से लिखा जा सकता है?
[EN] Yes, by writing a helper `printGivenLevel(root, level)` and looping `level` from 1 to `height(root)`, or passing a level index into a list of buckets. However, the naive height-loop approach takes O(n^2) worst-case time on skewed trees, whereas a FIFO Queue takes optimal O(n) time.
[HI] हाँ, प्रत्येक स्तर के लिए अलग रिकर्सिव फ़ंक्शन चलाकर ऐसा कर सकते हैं, लेकिन स्क्यूड ट्री पर यह O(n^2) समय लेता है; जबकि Queue वाली BFS विधि सटीक O(n) समय में चलती है।
Q2: Why does BFS take O(n) space on balanced trees while DFS takes O(log n)?
संतुलित ट्री पर BFS में O(n) स्पेस और DFS में O(log n) स्पेस क्यों लगता है?
[EN] DFS stores only a single root-to-leaf path on its stack (length = height = O(log n)), whereas BFS must simultaneously hold an entire horizontal frontier level—whose width reaches ceil(n/2) = O(n) at the bottom of a balanced tree.
[HI] DFS एक समय में केवल एक रूट-से-पत्ती मार्ग को स्टैक पर रखता है (ऊंचाई O(log n)), जबकि BFS को एक पूरे क्षैतिज स्तर के सभी नोड्स (जो तल पर लगभग n/2 होते हैं) कतार में एक साथ रखने पड़ते हैं।
Q3: How is Level Order Traversal related to Heap array storage?
लेवल ऑर्डर ट्रैवर्सल का बाइनरी हीप (Heap) के एरे प्रतिनिधित्व से क्या संबंध है?
[EN] A Complete Binary Tree stored sequentially in an array at indices 1..n (or 0..n-1) stores nodes in the exact Level Order (BFS) sequence!
[HI] किसी कम्प्लीट बाइनरी ट्री (या बाइनरी हीप) के एरे के इंडेक्स 1 से n तक तत्व ठीक उसी क्रम में होते हैं जो उसका लेवल ऑर्डर ट्रैवर्सल होता है!
Post a Comment
Post a Comment