PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम Constructing Binary Tree from Inorder and Preorder Traversals (इनऑर्डर और प्रीऑर्डर से बाइनरी ट्री का सटीक निर्माण) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।
Overview: A binary tree with distinct node values can be uniquely reconstructed from its Preorder and Inorder traversal arrays. Preorder identifies the subtree root from the left end, while Inorder partitions the remaining nodes into Left and Right subtrees—achieving O(n^2) naive time or O(n) optimal time with a hash-map index lookup.
अध्याय सार: भिन्न नोड मानों वाले किसी भी बाइनरी ट्री का अद्वितीय (Unique) निर्माण उसके प्रीऑर्डर और इनऑर्डर ट्रैवर्सल से किया जा सकता है। प्रीऑर्डर का पहला तत्व सबट्री का रूट बताता है और इनऑर्डर उस रूट के बाएं व दाएं सबट्री को विभाजित करता है; हैश-मैप इंडेक्स लुकअप से यह एल्गोरिदम O(n) समय में चलता है।
Constructing Binary Tree from Inorder and Preorder Traversals: Detailed Notes & Architecture (इनऑर्डर और प्रीऑर्डर से बाइनरी ट्री का सटीक निर्माण)
1. Uniqueness Theorem: Why Inorder Is Essential (अद्वितीयता प्रमेय: इनऑर्डर ट्रैवर्सल अनिवार्य क्यों है)
[EN] Any binary tree with distinct keys is uniquely determined by EITHER (Preorder + Inorder) OR (Postorder + Inorder). By contrast, (Preorder + Postorder) fails to uniquely identify an arbitrary binary tree whenever any node has only a single child: for instance, Preorder [1, 2] and Postorder [2, 1] match both a tree where 2 is 1's left child and a tree where 2 is 1's right child! Inorder breaks this tie because 2 before 1 ([2, 1]) means left child, whereas 1 before 2 ([1, 2]) means right child.
[HI] भिन्न मानों वाले ट्री को अद्वितीय रूप से बनाने के लिए (प्रीऑर्डर + इनऑर्डर) या (पोस्टऑर्डर + इनऑर्डर) में से एक जोड़ा जरूरी है। अकेला (प्रीऑर्डर + पोस्टऑर्डर) सामान्य ट्री नहीं बना सकता क्योंकि एकल चाइल्ड होने पर यह पता नहीं चलता कि चाइल्ड बायां है या दायां (जब तक ट्री फुल/स्ट्रिक्ट न हो)। इनऑर्डर बाएं व दाएं को अलग करके यह भ्रम समाप्त कर देता है।
2. Divide-and-Conquer Reconstruction Algorithm (डिवाइड-एंड-कॉन्कर पुनर्निर्माण एल्गोरिदम)
[EN] Given `pre[preStart..preEnd]` and `in[inStart..inEnd]`: (1) Pick `rootVal = pre[preStart]` as the current subtree root (using a global or reference `preIdx` advancing left-to-right). (2) Locate `pos` where `in[pos] == rootVal`. (3) Compute `leftCount = pos - inStart`. (4) Recursively construct `root->left` using `in[inStart .. pos-1]` and the next `leftCount` elements `pre[preStart+1 .. preStart+leftCount]`. (5) Recursively construct `root->right` using `in[pos+1 .. inEnd]` and `pre[preStart+leftCount+1 .. preEnd]`.
[HI] प्रीऑर्डर व इनऑर्डर से निर्माण के 5 चरण हैं: (1) प्रीऑर्डर का पहला तत्व `pre[preStart]` वर्तमान रूट बनाएं; (2) इनऑर्डर में इस रूट का इंडेक्स `pos` खोजें; (3) बाएं सबट्री की लंबाई `leftCount = pos - inStart` निकालें; (4) `inStart` से `pos-1` व अगले `leftCount` प्रीऑर्डर तत्वों से लेफ्ट सबट्री बनाएं; (5) `pos+1` से `inEnd` व शेष प्रीऑर्डर तत्वों से राइट सबट्री बनाएं।
3. Worked Dry-Run Example & Deriving Postorder (सॉल्व्ड उदाहरण व सीधे पोस्टऑर्डर निकालना)
[EN] Suppose Preorder = [A, B, D, E, C, F] and Inorder = [D, B, E, A, F, C]. Step 1: Root is A (first in Preorder); in Inorder, [D, B, E] sits left of A (length 3) and [F, C] sits right (length 2). Step 2: Left slice Preorder [B, D, E] + Inorder [D, B, E] makes B the root with left D and right E. Step 3: Right slice Preorder [C, F] + Inorder [F, C] makes C the root with left F and right NULL. Consequently, the Postorder of this uniquely built tree is [D, E, B, F, C, A].
[HI] उदाहरण: Pre = [A, B, D, E, C, F], In = [D, B, E, A, F, C]। प्रीऑर्डर का पहला अक्षर A रूट है; इनऑर्डर में A के बाईं ओर [D, B, E] (3 तत्व) तथा दाईं ओर [F, C] (2 तत्व) हैं। बायां भाग B को रूट बनाकर D को लेफ्ट व E को राइट रखता है, तथा दायां भाग C को रूट बनाकर F को लेफ्ट रखता है। इस निर्मित ट्री का पोस्टऑर्डर [D, E, B, F, C, A] प्राप्त होता है।
4. Time Complexity: O(n^2) Linear Scan vs O(n) Hash Map (समय जटिलता: O(n^2) लीनियर स्कैन बनाम O(n) हैश-मैप)
[EN] Searching for `rootVal` inside `in[inStart..inEnd]` via a linear loop costs O(n) per recursive call, degrading total reconstruction time to O(n^2) on a left-skewed tree (e.g., Preorder [5,4,3,2,1], Inorder [1,2,3,4,5]). Pre-populating a Hash Map `inIndex[val] = index` before recursion reduces each root lookup to O(1) expected time, achieving optimal O(n) overall time and O(n) auxiliary space. Note that duplicate key values invalidate uniqueness unless paired with extra structure info.
[HI] हर बार इनऑर्डर एरे में रूट को लीनियर सर्च से खोजने पर लेफ्ट-स्क्यूड ट्री में कुल समय O(n^2) हो जाता है। रिकर्सन से पहले इनऑर्डर के प्रत्येक मान का इंडेक्स एक हैश-मैप में सहेज लेने से खोज O(1) हो जाती है और पूरा निर्माण O(n) समय व O(n) स्पेस में पूर्ण होता है। ध्यान दें कि डुप्लीकेट मान होने पर अद्वितीय ट्री नहीं बन सकता।
Syntax, Formula & Technical Example (Constructing Binary Tree from Inorder and Preorder Traversals)
// O(n) Binary Tree Construction using Preorder + Inorder + HashMap
Node* build(int pre[], int* preIdx, int inStart, int inEnd, Map* inMap) {
if (inStart > inEnd) return NULL;
int rootVal = pre[(*preIdx)++];
Node* root = newNode(rootVal);
int pos = mapGet(inMap, rootVal); // O(1) lookup in Inorder
root->left = build(pre, preIdx, inStart, pos - 1, inMap);
root->right = build(pre, preIdx, pos + 1, inEnd, inMap);
return root;
}
Constructing Binary Tree from Inorder and Preorder Traversals Quick Reference & Comparison Table
| Reconstruction Aspect | Technical Rule / Complexity | Exam Note |
|---|---|---|
| Root Identification | First element of current Preorder slice | Advances sequentially with global preIdx++ |
| Subtree Partitioning | Split Inorder around root position `pos` | Left slice [inStart..pos-1]; Right [pos+1..inEnd] |
| Naive vs Optimal Time | O(n^2) linear scan vs O(n) Hash Map | Worst-case O(n^2) hits on left-skewed tree |
| Duplicate Keys Limitation | Requires all node keys to be distinct | Duplicates make `pos` lookup ambiguous |
Constructing Binary Tree from Inorder and Preorder Traversals Top 20 Bilingual MCQs with Answers
Q1. Which combination of traversals is sufficient to uniquely construct ANY binary tree (with distinct node keys)?
(भिन्न कुंजियों वाले किसी भी बाइनरी ट्री के अद्वितीय निर्माण के लिए कौन सा ट्रैवर्सल जोड़ा पर्याप्त है?)
(A) Preorder and Inorder
(B) Postorder alone
(C) Preorder and Postorder
(D) Preorder and Level Order
Correct Answer: (A)
[EN] Inorder is mandatory alongside either Preorder or Postorder to separate left and right subtrees unambiguously.
[HI] किसी भी सामान्य बाइनरी ट्री के निर्माण हेतु इनऑर्डर के साथ या तो प्रीऑर्डर या पोस्टऑर्डर होना अनिवार्य है।
Q2. When reconstructing a binary tree from Preorder and Inorder, how is the root of each subtree identified?
(प्रीऑर्डर और इनऑर्डर से ट्री बनाते समय प्रत्येक सबट्री का रूट कैसे पहचाना जाता है?)
(A) It is always the first element of the current Preorder slice
(B) It is the last element of the Preorder slice
(C) It is the smallest value in the Inorder slice
(D) It is always the middle element of the Inorder slice
Correct Answer: (A)
[EN] Because Preorder visits Node-Left-Right, the root always sits at index 0 of the active Preorder range.
[HI] प्रीऑर्डर N-L-R क्रम अपनाता है, अतः सक्रिय प्रीऑर्डर हिस्से का पहला तत्व ही हमेशा सबट्री का रूट होता है।
Q3. Once the root is located at index `pos` in `Inorder[inStart..inEnd]`, how many nodes belong to its left subtree?
(यदि रूट इनऑर्डर एरे `Inorder[inStart..inEnd]` के इंडेक्स `pos` पर मिलता है, तो इसके बाएं सबट्री में कितने नोड्स होंगे?)
(A) pos + 1
(B) pos - inStart
(C) inEnd - pos
(D) inEnd - inStart
Correct Answer: (B)
[EN] Every index from `inStart` up to `pos - 1` lies strictly in the left subtree, totaling `pos - inStart` nodes.
[HI] इनऑर्डर में `inStart` से `pos - 1` तक के सभी `pos - inStart` नोड्स बाएं सबट्री का हिस्सा होते हैं।
Q4. Why is the naive recursive tree construction from Preorder and Inorder O(n^2) in the worst case?
(प्रीऑर्डर और इनऑर्डर से ट्री निर्माण का साधारण (Naive) एल्गोरिदम सबसे खराब स्थिति में O(n^2) समय क्यों लेता है?)
(A) Because Preorder must be sorted at every level
(B) Because Postorder must be computed simultaneously
(C) Linear scanning `Inorder` to find the root at each step takes O(n) per node on a skewed tree
(D) Because creating n tree nodes takes O(n^2) heap memory
Correct Answer: (C)
[EN] On a left-skewed tree, each of n calls scans ~n/2 elements on average -> Theta(n^2) comparisons.
[HI] हर रिकर्सिव कॉल में इनऑर्डर में रूट को लीनियर सर्च से खोजने पर स्क्यूड ट्री में O(n^2) तुलनाएं होती हैं।
Q5. How can the time complexity of constructing a binary tree from Preorder and Inorder be reduced from O(n^2) to O(n)?
(प्रीऑर्डर और इनऑर्डर से ट्री बनाने की समय जटिलता को O(n^2) से घटाकर O(n) कैसे किया जाता है?)
(A) Replace pointers with a linked list
(B) Use an explicit stack instead of recursion
(C) Sort the Preorder array first
(D) Store every Inorder element's index in a Hash Map before recursion for O(1) lookup
Correct Answer: (D)
[EN] Precomputing value -> index in a hash table avoids repeated linear scans inside Inorder.
[HI] रिकर्सन से पहले इनऑर्डर के सभी तत्वों का इंडेक्स एक हैश-मैप में रखने से रूट की खोज O(1) समय में हो जाती है।
Q6. Given Preorder = [1, 2, 4, 5, 3, 6, 7] and Inorder = [4, 2, 5, 1, 6, 3, 7], what is the Postorder traversal?
(यदि Preorder = [1, 2, 4, 5, 3, 6, 7] और Inorder = [4, 2, 5, 1, 6, 3, 7] हो, तो ट्री का पोस्टऑर्डर क्या होगा?)
(A) 1, 2, 3, 4, 5, 6, 7
(B) 5, 4, 2, 7, 6, 3, 1
(C) 4, 5, 2, 6, 7, 3, 1
(D) 4, 2, 5, 6, 3, 7, 1
Correct Answer: (C)
[EN] Root 1; Left (root 2, children 4, 5) -> Post [4, 5, 2]; Right (root 3, children 6, 7) -> Post [6, 7, 3]; then 1.
[HI] रूट 1; बायां सबट्री [4, 5, 2]; दायां सबट्री [6, 7, 3]; अंत में 1 -> 4, 5, 2, 6, 7, 3, 1।
Q7. In the O(n) recursive `buildTree` function using a shared advancing index `preIdx`, which subtree MUST be constructed first?
(साझा इंडेक्स `preIdx++` का उपयोग करने वाले `buildTree` फ़ंक्शन में पहले किस सबट्री का निर्माण अनिवार्य है?)
(A) Right subtree first, then Left subtree
(B) Order does not matter
(C) Whichever subtree has more nodes
(D) Left subtree first, then Right subtree
Correct Answer: (D)
[EN] Because Preorder visits Node -> Left -> Right, advancing `preIdx++` sequentially encounters Left subtree nodes before Right subtree nodes.
[HI] चूंकि प्रीऑर्डर में रूट के तुरंत बाद बायां सबट्री आता है, इसलिए `preIdx++` क्रम सही रखने हेतु पहले लेफ्ट सबट्री बनाना जरूरी है।
Q8. Suppose Preorder = [10, 20, 30] and Inorder = [10, 20, 30]. What is the shape of the reconstructed tree?
(यदि Preorder = [10, 20, 30] और Inorder = [10, 20, 30] हो, तो निर्मित होने वाले ट्री का आकार कैसा होगा?)
(A) Strictly Right-Skewed (10 -> right 20 -> right 30)
(B) Balanced Perfect Tree rooted at 20
(C) Complete Tree rooted at 10 with left=20, right=30
(D) Strictly Left-Skewed
Correct Answer: (A)
[EN] Root 10 sits at index 0 of Inorder, meaning 0 nodes lie in its left subtree; repeat for 20 -> strictly right-skewed.
[HI] 10 के बाईं ओर इनऑर्डर में कोई तत्व नहीं है, इसी तरह 20 के बाईं ओर कोई नहीं—अतः यह पूरी तरह राइट-स्क्यूड ट्री है।
Q9. Suppose Preorder = [10, 20, 30] and Inorder = [30, 20, 10]. What is the shape of the reconstructed tree?
(यदि Preorder = [10, 20, 30] और Inorder = [30, 20, 10] हो, तो निर्मित होने वाले ट्री का आकार कैसा होगा?)
(A) Strictly Right-Skewed
(B) Invalid traversal pair
(C) Balanced tree rooted at 20
(D) Strictly Left-Skewed (10 -> left 20 -> left 30)
Correct Answer: (D)
[EN] Root 10 is at the far right of Inorder, placing [30, 20] entirely in its left subtree; repeat for 20 -> left-skewed.
[HI] 10 इनऑर्डर के सबसे दाहिने छोर पर है अर्थात 20 व 30 इसके बाएं सबट्री में हैं, अतः ट्री लेफ्ट-स्क्यूड बनेगा।
Q10. Given Preorder = [A, B, C, D, E] and Inorder = [B, A, D, C, E], which node is the right child of A?
(यदि Preorder = [A, B, C, D, E] और Inorder = [B, A, D, C, E] हो, तो नोड A का राइट चाइल्ड कौन है?)
(A) C
(B) D
(C) E
(D) B
Correct Answer: (A)
[EN] Root A splits Inorder into Left=[B] and Right=[D, C, E]. Next in Preorder after [A, B] is C, which becomes root of Right=[D, C, E]!
[HI] A के बाएं [B] और दाएं [D, C, E] हैं; प्रीऑर्डर में A व B के बाद C आता है, अतः C ही दायां चाइल्ड/रूट होगा।
Q11. For what special class of binary trees CAN Preorder and Postorder uniquely reconstruct the tree without Inorder?
(किस विशेष प्रकार के बाइनरी ट्री के लिए बिना इनऑर्डर के भी केवल प्रीऑर्डर और पोस्टऑर्डर से अद्वितीय निर्माण संभव है?)
(A) Left-Skewed Binary Tree
(B) Full (Strict) Binary Tree (every node has 0 or 2 children)
(C) Complete Binary Tree only
(D) Degenerate Binary Tree
Correct Answer: (B)
[EN] When every internal node must have either 0 or 2 children, the single-child left/right ambiguity disappears completely.
[HI] फुल (स्ट्रिक्ट) बाइनरी ट्री में 1 चाइल्ड वाली स्थिति होती ही नहीं (या तो 0 या 2), इसलिए लेफ्ट/राइट भ्रम नहीं रहता।
Q12. What happens to the reconstruction algorithm if Preorder = [1, 2, 3] and Inorder = [1, 3, 2], vs Preorder = [1, 2, 3] and Inorder = [3, 1, 2]?
(यदि Preorder = [1, 2, 3] और Inorder = [3, 1, 2] दिया जाए, तो क्या यह एक वैध बाइनरी ट्री बनाता है?)
(A) Yes, rooted at 1 with left=3, right=2
(B) Yes, producing a Complete tree
(C) Yes, rooted at 3
(D) No — it is an inconsistent/invalid traversal pair because left slice [3] conflicts with Preorder's 2
Correct Answer: (D)
[EN] Root 1 splits Inorder into Left=[3] (size 1), which demands the next Preorder item be 3—contradicting Preorder's actual next item 2!
[HI] इनऑर्डर में 1 के बाएं [3] है जबकि प्रीऑर्डर में 1 के ठीक बाद 2 आ रहा है—अतः यह असंगत (Invalid) जोड़ा है।
Q13. Why must node values be unique (distinct) for standard Preorder + Inorder reconstruction?
(मानक प्रीऑर्डर + इनऑर्डर पुनर्निर्माण के लिए ट्री के सभी नोड्स के मान अद्वितीय (Distinct) होना क्यों आवश्यक है?)
(A) Because duplicate values create multiple matching indices in Inorder, making left/right partitioning ambiguous
(B) Because Preorder drops duplicates automatically
(C) Because duplicate nodes break recursion stacks
(D) Because hash maps cannot store duplicate keys
Correct Answer: (A)
[EN] For example, Preorder [2, 2] and Inorder [2, 2] match both a left-child tree and a right-child tree.
[HI] समान मान होने पर इनऑर्डर में यह तय नहीं हो पाता कि कौन सा इंडेक्स रूट है और कौन सा चाइल्ड (जैसे [2, 2])।
Q14. Which statement is NOT true about reconstructing a binary tree from Preorder and Inorder?
(प्रीऑर्डर और इनऑर्डर से बाइनरी ट्री के निर्माण के विषय में इनमें से कौन सा कथन असत्य (NOT true) है?)
(A) Preorder + Inorder allows computing Postorder directly without even building full pointer nodes
(B) Two distinct binary trees with unique keys can share the exact same Preorder and Inorder sequences
(C) Preorder + Inorder takes O(n) time using a hash map
(D) Recursion call stack takes O(h) space
Correct Answer: (B)
[EN] Uniqueness Theorem guarantees that distinct-key Preorder + Inorder map to at most ONE binary tree structure.
[HI] प्रमेय के अनुसार भिन्न मानों वाले समान प्रीऑर्डर व इनऑर्डर से दो अलग-अलग ट्री कभी नहीं बन सकते।
Q15. What is the auxiliary space complexity of the Hash-Map optimized `buildTree` algorithm on an n-node tree?
(n नोड्स वाले ट्री के लिए हैश-मैप अनुकूलित `buildTree` एल्गोरिदम की अतिरिक्त स्पेस जटिलता क्या है?)
(A) O(n^2)
(B) O(n) for the hash map plus O(h) recursion stack (total O(n))
(C) O(1)
(D) O(log n) total including hash map
Correct Answer: (B)
[EN] Storing all n Inorder indices in the map requires O(n) space regardless of tree height h.
[HI] इनऑर्डर के सभी n मानों को हैश-मैप में सहेजने के कारण कुल अतिरिक्त स्पेस जटिलता O(n) होती है।
Q16. Given Preorder = [F, B, A, D, C, E, G, I, H] and Inorder = [A, B, C, D, E, F, G, H, I], what is the right child of G?
(यदि Preorder = [F, B, A, D, C, E, G, I, H] और Inorder = [A, B, C, D, E, F, G, H, I] है, तो नोड G का राइट चाइल्ड कौन है?)
(A) E
(B) F
(C) H
(D) I
Correct Answer: (D)
[EN] Root F splits Right Inorder=[G, H, I] with corresponding Preorder=[G, I, H]. Root is G, left is empty (nothing left of G in [G,H,I]), next in Preorder is I as G's right child (with H as I's left child).
[HI] F के दाईं ओर [G, H, I] है और प्रीऑर्डर [G, I, H] है; G के बाएं कुछ नहीं है, अतः G का राइट चाइल्ड I (और I का लेफ्ट H) है।
Q17. Within Constructing Binary Tree from Inorder and Preorder Traversals, which reconstruction aspect directly maps to: "First element of current Preorder slice"?
(Constructing Binary Tree from Inorder and Preorder Traversals में कौन सा Reconstruction Aspect सीधे "First element of current Preorder slice" से संबंधित है?)
(A) Naive vs Optimal Time
(B) Duplicate Keys Limitation
(C) Root Identification
(D) Subtree Partitioning
Correct Answer: (C)
[EN] In Constructing Binary Tree from Inorder and Preorder Traversals, 'Root Identification' handles 'First element of current Preorder slice' (Advances sequentially with global preIdx++).
[HI] Constructing Binary Tree from Inorder and Preorder Traversals में 'Root Identification' का कार्य/विवरण 'First element of current Preorder slice' (Advances sequentially with global preIdx++) है।
Q18. Which option accurately describes 'Subtree Partitioning' in Constructing Binary Tree from Inorder and Preorder Traversals?
(Constructing Binary Tree from Inorder and Preorder Traversals के संदर्भ में 'Subtree Partitioning' की सही विशेषता कौन सी है?)
(A) First element of current Preorder slice
(B) O(n^2) linear scan vs O(n) Hash Map
(C) Requires all node keys to be distinct
(D) Split Inorder around root position `pos`
Correct Answer: (D)
[EN] 'Subtree Partitioning' provides 'Split Inorder around root position `pos`' — key point: Left slice [inStart..pos-1]; Right [pos+1..inEnd].
[HI] 'Subtree Partitioning' का मुख्य विवरण 'Split Inorder around root position `pos`' है (Left slice [inStart..pos-1]; Right [pos+1..inEnd])।
Q19. In Constructing Binary Tree from Inorder and Preorder Traversals, identify the correct parameter for the specification: "O(n^2) linear scan vs O(n) Hash Map".
(Constructing Binary Tree from Inorder and Preorder Traversals में "O(n^2) linear scan vs O(n) Hash Map" विवरण किस विकल्प के लिए सही है?)
(A) Subtree Partitioning
(B) Naive vs Optimal Time
(C) Duplicate Keys Limitation
(D) Root Identification
Correct Answer: (B)
[EN] 'Naive vs Optimal Time' corresponds to 'O(n^2) linear scan vs O(n) Hash Map' (Worst-case O(n^2) hits on left-skewed tree).
[HI] 'Naive vs Optimal Time' का संबंध 'O(n^2) linear scan vs O(n) Hash Map' (Worst-case O(n^2) hits on left-skewed tree) से है।
Q20. Considering Constructing Binary Tree from Inorder and Preorder Traversals, what key behavior defines 'Duplicate Keys Limitation'?
(Constructing Binary Tree from Inorder and Preorder Traversals में 'Duplicate Keys Limitation' की मुख्य भूमिका या मान क्या है?)
(A) Requires all node keys to be distinct
(B) O(n^2) linear scan vs O(n) Hash Map
(C) Split Inorder around root position `pos`
(D) First element of current Preorder slice
Correct Answer: (A)
[EN] 'Duplicate Keys Limitation' represents 'Requires all node keys to be distinct' (Duplicates make `pos` lookup ambiguous).
[HI] 'Duplicate Keys Limitation' का अर्थ/मान 'Requires all node keys to be distinct' है (Duplicates make `pos` lookup ambiguous)।
Constructing Binary Tree from Inorder and Preorder Traversals — Exam FAQs
Q1: Can we find the Postorder traversal directly from Preorder and Inorder without allocating tree nodes in memory?
क्या हम बिना मेमोरी में ट्री नोड्स बनाए सीधे प्रीऑर्डर और इनऑर्डर से पोस्टऑर्डर निकाल सकते हैं?
[EN] Yes! Simply recurse on the left slice, then recurse on the right slice, and print the current Preorder root value at the end of the function—effectively simulating Postorder (L-R-N) directly.
[HI] हाँ! पहले लेफ्ट हिस्से पर रिकर्सन, फिर राइट हिस्से पर रिकर्सन और फ़ंक्शन के अंत में वर्तमान रूट प्रिंट करके बिना नोड बनाए सीधे पोस्टऑर्डर प्रिंट किया जा सकता है।
Q2: Why can't Preorder and Postorder uniquely rebuild a general binary tree?
प्रीऑर्डर और पोस्टऑर्डर मिलकर किसी भी सामान्य बाइनरी ट्री का निर्माण क्यों नहीं कर सकते?
[EN] Whenever a node has only one child (say A has child B), Preorder is [A, B] and Postorder is [B, A] regardless of whether B is A's left child or right child.
[HI] यदि किसी नोड A का केवल एक चाइल्ड B हो, तो B चाहे लेफ्ट में हो या राइट में, प्रीऑर्डर [A, B] और पोस्टऑर्डर [B, A] दोनों स्थितियों में बिल्कुल एक जैसा रहता है।
Q3: How do you reconstruct a Binary Tree from Postorder and Inorder?
पोस्टऑर्डर और इनऑर्डर से बाइनरी ट्री कैसे बनाया जाता है?
[EN] It mirrors Preorder + Inorder, except you pick the subtree root from the END of Postorder (`postIdx--`) and MUST build the Right subtree BEFORE the Left subtree.
[HI] बिल्कुल इसी तरह होता है, बस रूट पोस्टऑर्डर के अंतिम सिरे से लिया जाता है और `postIdx--` घटाते समय पहले राइट सबट्री और फिर लेफ्ट सबट्री बनाया जाता है।
Post a Comment
Post a Comment