Stack applications और binary-tree reconstruction
उद्देश्य और स्पष्ट conventions
पहले से पढ़े stack को postfix evaluation तथा delimiter matching में लगाएँ। फिर traversal orders से binary tree reconstruct करें और uniqueness/height समझें। ये ordinary ordered binary trees हैं, जरूरी नहीं BST: left/right positions महत्वपूर्ण हैं। Counterexample में अलग न कहें तो labels distinct हैं। Height edges में है; empty tree −1, leaf 0। Full में हर node के zero या दो children; complete में आखिरी level छोड़कर सब भरे और आखिरी left-to-right भरा; perfect में हर internal node के दो बच्चे और सभी leaves समान depth पर। ये शब्द interchangeable नहीं।
1. Postfix evaluation में operand order
Tokens स्पष्ट अलग हैं; "12" एक operand है, 1 और 2 नहीं। उदाहरण binary +,−,× तथा छोटे exact integers के हैं; overflow/division ambiguity नहीं। Left-to-right scan करें। Operand push करें। Binary operator पर कम-से-कम दो entries चाहिए: पहले right operand b pop, फिर left a; a op b निकालकर push करें। अंत में ठीक एक value होनी चाहिए। Scan में कमी underflow है; अंत में extra values हों तो एक complete expression नहीं।
8 3 2 * − 4 + का bottom-to-top stack trace:
8 : [8] 3 : [8,3] 2 : [8,3,2]
- : [8,6]
− : [2] 4 : [2,4] + : [6]
Subtraction पर b=6,a=8, इसलिए 2 push, −2 नहीं। m tokens में हर token एक बार process: O(m) time, worst-case O(m) stack। इस trace का maximum occupancy 3। Counts आवश्यक हैं, पर्याप्त नहीं: binary expression में operands=operators+1 चाहिए, लेकिन + 2 3 count satisfy करके भी शुरू में underflow करता है। Unary operators हों तो अलग arity rule चाहिए।
2. Balanced delimiters में type और nesting
(),[],{} वाले stream में opening delimiter push करें। Closing delimiter पर stack nonempty और top matching opening होना चाहिए, फिर pop। इस simplified contract में अन्य tokens ignore हैं; पूरे source code के quoted strings/comments के लिए lexical analysis चाहिए, जो यहाँ बाहर है। End पर empty stack तभी accept।
([{}]) में (, [, { push; } से { pop, ] से [ pop, ) से ( pop: accept। ([)] में ) आते समय top [ है, इसलिए तुरंत reject, भले सभी types के opening/closing counts बराबर हों। (() के अंत में opening बचा है; )( के शुरू में underflow। एक delimiter type के लिए counter तभी पर्याप्त है जब हर prefix nonnegative तथा final zero हो। Multiple types में केवल अलग counts पर्याप्त नहीं; nesting/type चाहिए। समय O(m), stack O(d), जहाँ d maximum nesting depth और d≤m।
3. Inorder से subtree split और reconstruction
Preorder root,left,right; inorder left,root,right; postorder left,right,root है। Distinct labels तथा valid consistent sequences में preorder+inorder unique ordered binary tree तय करते हैं। पहला preorder label root, inorder में उसकी position से left/right split। इन parts के sizes बताते हैं कि आगे कितने preorder labels प्रत्येक subtree में हैं। Paired slices पर recurse करें। Inorder+postorder भी unique है: आखिरी postorder root और sizes से slices। Shared index से postorder backward consume करें तो right subtree पहले, left बाद में बनाएँ।
उदाहरण preorder A B D E C F; inorder D B E A C F। Root A से inorder D B E तथा C F में split। अगले तीन preorder labels B D E left subtree हैं: B root, D और E बच्चे। Right preorder C F तथा inorder C F में C root, left absent,right F। पूरा postorder D E B F C A; height 2। यह subtree-size आधारित है, alphabetical sorting नहीं; यहाँ BST ordering नहीं।
Result से पहले lengths/label sets समान, theorem के लिए labels distinct, और हर root current inorder slice में होना चाहिए। केवल equal sets consistency सिद्ध नहीं करते। Preorder A B C तथा inorder C A B inconsistent हैं: A root को left में C चाहिए, पर preorder उस one-node subtree में B देता है। हर inorder root linear search करने पर worst-case O(n²)। O(1)-access label→inorder-position lookup तथा repeated copying के बजाय index ranges से construction O(n) time, lookup storage O(n), recursion stack O(h+1)। Hash table में O(1) lookup सामान्यतः expected है, जब तक stronger guarantee न हो।
4. Preorder+postorder की ambiguity
Preorder A B तथा postorder B A में A root और B sole child है। B left या right, दोनों trees match करते हैं। इसलिए distinct labels पर भी ये traversals सामान्यतः shape नहीं तय करते। यदि distinct labels और full binary tree contract हो, तो consistent preorder/postorder unique ordered tree तय करते हैं: हर nonleaf के दो बच्चे; अगला preorder root, postorder में left subtree का endpoint देता है; बाकी right subtree है। यह extra contract one-child ambiguity हटाता है, arbitrary tree में silently न मानें। Repeated labels होने पर inorder के साथ भी root के कई split positions हो सकते हैं और uniqueness टूट सकती है।
5. Shape bounds और stack depth
Depth d पर अधिकतम 2^d nodes। Edge-height h तक sum से n≤2^(h+1)−1। n≥1 में ceil(log2(n+1))−1≤h≤n−1; maximum chain में, minimum-height shape upper levels पर्याप्त भरती है। इससे हर n-node tree logarithmic-height नहीं होता। Complete n-node tree में h=floor(log2 n)। Full tree में I internal nodes हों तो L=I+1 leaves तथा n=2I+1: 2I child edges, कुल n−1 edges के बराबर। Full tree आवश्यक नहीं perfect/logarithmic-height: comb-shaped full tree की height n में linear हो सकती है।
n=7 ordinary binary tree की height 2 से 6 तक हो सकती है। सात-node full tree की height 3 भी हो सकती है; full से height 2 नहीं निकलती। Chain पर recursive traversal/reconstruction का stack O(n), balanced-height tree पर O(log n)। कुल O(n) visits का अर्थ हर shape में O(n) simultaneous stack entries नहीं।
गलतियों की checklist
Token boundaries तथा arity घोषित करें, right operand पहले pop करें। हर close और end पर delimiters validate करें। Reconstruction में distinctness, traversal pair तथा full-tree promise लिखें। Uniqueness से पहले slices consistent हों। Height में edges/nodes स्पष्ट करें; actual shape को possible minimum-height shape न मानें।
मौलिक अभ्यास: छह single-correct MCQs
ये मौलिक शिक्षण प्रश्न हैं, previous-year questions नहीं। एक विकल्प चुनें।
P01. Binary operators से postfix 8 3 2 * − 4 + evaluate करें।
A. −6 B. 2 C. 6 D. 10
उत्तर: C
A: Operands का क्रम गलत है।
B: यह 4 जोड़ने से पहले intermediate value है।
C: 3×2=6,8−6=2,2+4=6।
D: Grouping (8−3×2)+4 है।
P02. हर type के equal opening/closing counts के बावजूद कौन reject होगा?
A. ([]) B. ([)] C. {()} D. [{}]
उत्तर: B
A: Types/nesting match हैं।
B: ) पर top [ है; nesting गलत।
C: Types/nesting match हैं।
D: Types/nesting match हैं।
P03. Preorder A B D E C F और inorder D B E A C F का postorder?
A. D E B F C A B. D B E F C A C. A B D E C F D. D E B C F A
उत्तर: A
A: Left D,E,B; right F,C; अंत में root A।
B: Postorder में B दोनों बच्चों के बाद है।
C: यह preorder है।
D: F, C का right child है; C से पहले होगा।
P04. Distinct labels में preorder A B,postorder B A; full-tree promise नहीं। क्या तय होता है?
A. ठीक एक ordered tree B. कोई valid tree नहीं C. Unique BST D. दो ordered tree shapes
उत्तर: D
A: Sole child की side नहीं पता।
B: दोनों one-child placements valid हैं।
C: BST order contract दिया नहीं।
D: B, A का left या right child हो सकता है।
P05. Ordinary सात-node binary tree के possible minimum/maximum edge-heights?
A. 3 और 7 B. 2 और 6 C. 2 और 2 D. 0 और 6
उत्तर: B
A: ये path nodes गिनते हैं, edges नहीं।
B: Perfect shape height 2; chain height 6।
C: सभी shapes perfect/balanced नहीं।
D: Height zero में एक ही node।
P06. Full binary tree में 9 internal nodes हैं। Leaves कितने?
A. 9 B. 18 C. 10 D. 19
उत्तर: C
A: Full tree में leaves internal से एक अधिक हैं।
B: 18 child edges हैं।
C: L=I+1=10।
D: 19 total nodes 2I+1 हैं।
स्रोत और दायरा
GATE CS 2026 के मौजूदा आधार-पाठों का सीमित विस्तार। पूरे विषय की पूर्णता का दावा नहीं। उदाहरण और प्रश्न मौलिक हैं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन