Binary Tree Traversals: Preorder Traversal (N-L-R) Notes in Hindi & English : प्रीऑर्डर ट्रैवर्सल (Node-Left-Right): रूट पहले देखना और 20 महत्वपूर्ण MCQ प्रश्न (Rajasthan IT Exam)

Post a Comment

PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम Binary Tree Traversals: Preorder Traversal (N-L-R) (प्रीऑर्डर ट्रैवर्सल (Node-Left-Right): रूट पहले देखना) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।

Overview: Preorder Traversal (N-L-R) visits the current Root node first before recursively exploring the Left subtree and then the Right subtree. Because the parent is always processed ahead of its descendants, Preorder naturally generates Prefix (Polish) expressions, clones tree structures top-down, and uniquely reconstructs a BST when inserted sequentially.

अध्याय सार: प्रीऑर्डर ट्रैवर्सल (Node-Left-Right) एक डेप्थ-फर्स्ट ट्रैवर्सल है जिसमें पहले वर्तमान रूट नोड को विज़िट किया जाता है और उसके बाद क्रमशः बाएं और दाएं सबट्री को देखा जाता है। रूट पहले प्रोसेस होने के कारण यह प्रीफिक्स (Prefix/Polish) व्यंजक बनाने, ट्री की हूबहू कॉपी करने तथा BST को पुनर्निर्मित करने में अत्यंत उपयोगी है।

Binary Tree Traversals: Preorder Traversal (N-L-R): Detailed Notes & Architecture (प्रीऑर्डर ट्रैवर्सल (Node-Left-Right): रूट पहले देखना)

1. N-L-R Top-Down Traversal Mechanics (N-L-R टॉप-डाउन ट्रैवर्सल की कार्यप्रणाली)

[EN] In Preorder Traversal (Node -> Left -> Right), the root of the entire tree—and the root of every subtree—always appears as the very first item in its traversal slice. Recursive execution processes `root->data` immediately upon entering the call, then invokes `preorder(root->left)`, and finally `preorder(root->right)`. Like other DFS traversals, it visits all n nodes in O(n) time and uses O(h) call-stack space.

[HI] प्रीऑर्डर ट्रैवर्सल (Node -> Left -> Right) में पूरे ट्री का रूट (तथा हर सबट्री का रूट) हमेशा अपने हिस्से में सबसे पहले आता है। रिकर्सिव फ़ंक्शन में प्रवेश करते ही नोड को प्रोसेस किया जाता है, फिर लेफ्ट सबट्री और अंत में राइट सबट्री कॉल होता है। इसकी समय जटिलता O(n) तथा कॉल स्टैक स्पेस O(h) होता है।

2. Iterative Stack Implementation: Push Right Before Left (इटरेटिव स्टैक विधि: राइट चाइल्ड पहले पुश करने का नियम)

[EN] Iterative Preorder uses a single LIFO stack initialized with `root`. Inside the loop, we pop `curr`, visit `curr->data`, push `curr->right` (if non-NULL), and THEN push `curr->left` (if non-NULL). Pushing the right child BEFORE the left child is critical because a stack pops in Last-In-First-Out order—ensuring the left child sits on top of the stack and is processed immediately next.

[HI] इटरेटिव प्रीऑर्डर में एक स्टैक में पहले रूट डाला जाता है। लूप में नोड पॉप कर प्रिंट करते हैं, और फिर पहले राइट चाइल्ड (यदि मौजूद हो) व उसके बाद लेफ्ट चाइल्ड को स्टैक में पुश करते हैं। राइट को पहले पुश करना अनिवार्य है ताकि LIFO स्टैक से लेफ्ट चाइल्ड पहले बाहर आए।

3. Prefix Expressions & Top-Down Tree Cloning (प्रीफिक्स व्यंजक व ट्री क्लोनिंग अनुप्रयोग)

[EN] Running Preorder on an Arithmetic Expression Tree emits Prefix (Polish) notation—such as `+ * A B C`—which eliminates parentheses and can be evaluated unambiguously from right to left. Furthermore, Preorder is the standard choice for cloning/deep-copying a binary tree or serializing it with sentinel markers (like `#` for NULL), because a parent node must be allocated before attaching its left and right children.

[HI] अंकगणितीय एक्सप्रेशन ट्री पर प्रीऑर्डर चलाने से प्रीफिक्स (Polish) नोटेशन मिलता है जिसमें कोष्ठकों की आवश्यकता नहीं रहती। साथ ही, किसी ट्री की डीप कॉपी (Cloning) या सीरियलाइजेशन में प्रीऑर्डर उपयोग होता है क्योंकि बच्चों को जोड़ने से पहले पेरेंट नोड का निर्माण जरूरी है।

4. Unique BST Reconstruction Property (प्रीऑर्डर से BST का अद्वितीय पुनर्निर्माण)

[EN] While Preorder alone cannot uniquely rebuild an arbitrary binary tree, Preorder sequence of a Binary Search Tree DOES uniquely determine the exact BST! Simply inserting the elements of a valid BST Preorder array one by one into an empty BST recreates the identical tree—or even faster, an O(n) upper-bound algorithm rebuilds it directly in linear time because BST's implicit Inorder is simply the sorted keys.

[HI] सामान्य बाइनरी ट्री के लिए अकेला प्रीऑर्डर पर्याप्त नहीं होता, पर किसी BST के प्रीऑर्डर क्रम के तत्वों को एक-एक कर खाली BST में डालने पर हूबहू वही BST दोबारा बन जाता है (क्योंकि BST का इनऑर्डर स्वतः ही सॉर्टेड क्रम होता है)।

Syntax, Formula & Technical Example (Binary Tree Traversals: Preorder Traversal (N-L-R))

// Recursive and Iterative Preorder Traversal (N-L-R)
void preorderRec(Node* root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    preorderRec(root->left);
    preorderRec(root->right);
}
void preorderIter(Node* root) {
    if (!root) return; Stack s; push(&s, root);
    while (!isEmpty(&s)) {
        Node* curr = pop(&s); printf("%d ", curr->data);
        if (curr->right) push(&s, curr->right); // Push Right FIRST
        if (curr->left)  push(&s, curr->left);  // Push Left SECOND
    }
}

Binary Tree Traversals: Preorder Traversal (N-L-R) Quick Reference & Comparison Table

Preorder FeatureRule / MechanismExam Significance
Visit OrderNode (Root) -> Left -> RightRoot is always the very first element emitted
Iterative Stack Push OrderPush Right child first, then LeftLIFO stack guarantees Left pops before Right
Expression Tree ResultPrefix (Polish) NotationParentheses-free operator-first form
Primary Structural UseTree Cloning & Folder Hierarchy ListingParent created/printed before children

Binary Tree Traversals: Preorder Traversal (N-L-R) Top 20 Bilingual MCQs with Answers

Q1. In Preorder Traversal (N-L-R), which node of a non-empty binary tree is ALWAYS printed first?

(प्रीऑर्डर ट्रैवर्सल (N-L-R) में किसी भी गैर-खाली बाइनरी ट्री का कौन सा नोड सदैव सबसे पहले प्रिंट होता है?)

(A) The minimum key node

(B) The Root node

(C) The leftmost leaf node

(D) The rightmost leaf node

Correct Answer: (B)

[EN] Preorder visits Node before Left and Right subtrees, so the global root is always the first output.

[HI] प्रीऑर्डर में सबसे पहले रूट (Node) को विज़िट किया जाता है, फिर लेफ्ट व राइट सबट्री।

Q2. When implementing Preorder Traversal iteratively with a stack, in what order must non-NULL children of the popped node be pushed?

(स्टैक द्वारा इटरेटिव प्रीऑर्डर ट्रैवर्सल में पॉप किए गए नोड के बच्चों को किस क्रम में स्टैक पर पुश करना चाहिए?)

(A) Push Left child first, then push Right child

(B) Push Right child first, then push Left child

(C) Push only Left child

(D) Push parent again

Correct Answer: (B)

[EN] Because a stack is LIFO, pushing Left second guarantees Left sits on top and gets popped before Right.

[HI] स्टैक LIFO होता है, इसलिए राइट को पहले और लेफ्ट को बाद में पुश करने पर लेफ्ट पहले पॉप होगा।

Q3. What notation does Preorder Traversal produce when applied to a binary Expression Tree?

(बाइनरी एक्सप्रेशन ट्री पर प्रीऑर्डर ट्रैवर्सल लागू करने पर किस प्रकार का व्यंजक प्राप्त होता है?)

(A) Postfix (Reverse Polish) Notation

(B) Prefix (Polish) Notation

(C) Infix Notation

(D) Three-Address Code

Correct Answer: (B)

[EN] Operators reside at internal parent nodes and are visited before their operand subtrees, yielding Prefix form.

[HI] ऑपरेटर (रूट) को बाएं और दाएं ऑपरेंड्स से पहले विज़िट करने पर प्रीफिक्स (Polish) नोटेशन मिलता है।

Q4. Given Root = 1, Left = 2 (Left = 4, Right = 5), and Right = 3 (Left = 6), what is the Preorder sequence?

(रूट 1, लेफ्ट 2 (लेफ्ट=4, राइट=5) व राइट 3 (लेफ्ट=6) वाले बाइनरी ट्री का प्रीऑर्डर क्रम क्या होगा?)

(A) 1, 2, 4, 5, 3, 6

(B) 4, 2, 5, 1, 6, 3

(C) 1, 2, 3, 4, 5, 6

(D) 4, 5, 2, 6, 3, 1

Correct Answer: (A)

[EN] N-L-R visits 1 -> Left(2 -> 4 -> 5) -> Right(3 -> 6) = 1, 2, 4, 5, 3, 6.

[HI] N-L-R क्रम: पहले 1, फिर लेफ्ट सबट्री (2, 4, 5), फिर राइट सबट्री (3, 6) = 1, 2, 4, 5, 3, 6।

Q5. Which traversal order is best suited to create a deep copy (clone) of a binary tree top-down?

(किसी बाइनरी ट्री की हूबहू कॉपी (Deep Copy / Clone) ऊपर से नीचे बनाने के लिए कौन सा ट्रैवर्सल सबसे उपयुक्त है?)

(A) Preorder Traversal

(B) Postorder Traversal

(C) Reverse Inorder

(D) Bottom-up Level Order

Correct Answer: (A)

[EN] Preorder allocates the parent node first so newly cloned left and right subtrees attach directly to it.

[HI] प्रीऑर्डर पहले नया रूट नोड बनाता है जिससे बाएं और दाएं क्लोन सबट्री आसानी से जुड़ सकें।

Q6. If a Binary Search Tree has Preorder traversal [15, 10, 8, 12, 20, 25], what is the root of its right subtree?

(यदि किसी BST का प्रीऑर्डर ट्रैवर्सल [15, 10, 8, 12, 20, 25] है, तो इसके राइट सबट्री का रूट क्या होगा?)

(A) 12

(B) 15

(C) 25

(D) 20

Correct Answer: (D)

[EN] 15 is the global root; [10, 8, 12] are < 15 (left subtree), and the first value > 15 is 20 (root of right subtree).

[HI] 15 मुख्य रूट है; 15 से छोटे [10, 8, 12] बाएं सबट्री में जाएंगे और 15 से बड़ा पहला तत्व 20 दाएं सबट्री का रूट होगा।

Q7. Can you uniquely reconstruct a Binary Search Tree solely from its Preorder sequence (distinct keys)?

(क्या केवल प्रीऑर्डर क्रम (भिन्न कुंजियों वाले) से एक बाइनरी सर्च ट्री (BST) का सटीक पुनर्निर्माण संभव है?)

(A) Only for trees with height <= 3

(B) Only if the tree is Complete

(C) No — Postorder is mandatory

(D) Yes — because sorting the Preorder sequence automatically provides its Inorder sequence

Correct Answer: (D)

[EN] Sorting the BST Preorder gives Inorder, and Preorder + Inorder uniquely determine any binary tree.

[HI] हाँ — BST के प्रीऑर्डर को सॉर्ट करने पर उसका इनऑर्डर मिल जाता है, और दोनों मिलकर अद्वितीय ट्री बना देते हैं।

Q8. On an Expression Tree for `(A + B) * (C - D)`, what is the Preorder output?

(`(A + B) * (C - D)` के एक्सप्रेशन ट्री का प्रीऑर्डर आउटपुट क्या होगा?)

(A) + * A B - C D

(B) A + B * C - D

(C) * + A B - C D

(D) A B + C D - *

Correct Answer: (C)

[EN] Root `*` comes first, left subtree `+ A B`, right subtree `- C D`, giving `* + A B - C D`.

[HI] मुख्य ऑपरेटर `*` पहले, फिर लेफ्ट `+ A B`, फिर राइट `- C D`, अर्थात `* + A B - C D`।

Q9. If a binary tree is strictly Left-Skewed with keys A (root) -> B -> C -> D, how do its Preorder and Postorder relate?

(यदि कोई ट्री पूरी तरह लेफ्ट-स्क्यूड (रूट A -> B -> C -> D) हो, तो उसके प्रीऑर्डर व पोस्टऑर्डर में क्या संबंध होगा?)

(A) Preorder and Postorder are identical

(B) Preorder and Inorder are identical

(C) Postorder (D, C, B, A) is the exact reverse of Preorder (A, B, C, D)

(D) Postorder is A, C, B, D

Correct Answer: (C)

[EN] With zero right children, N-L-R outputs A, B, C, D while L-R-N outputs D, C, B, A—exact reverse!

[HI] राइट चाइल्ड न होने पर प्रीऑर्डर A, B, C, D और पोस्टऑर्डर ठीक इसका उल्टा D, C, B, A होता है।

Q10. If a binary tree is strictly Right-Skewed (1 -> 2 -> 3 -> 4), which two traversals produce the EXACT SAME sequence?

(एक पूरी तरह राइट-स्क्यूड ट्री (1 -> 2 -> 3 -> 4) में कौन से दो ट्रैवर्सल बिल्कुल समान परिणाम देते हैं?)

(A) Preorder and Inorder (both yield 1, 2, 3, 4)

(B) Preorder and Postorder

(C) Postorder and Reverse Level Order

(D) Inorder and Postorder

Correct Answer: (A)

[EN] With empty left subtrees at every node, N-L-R (Preorder) and L-N-R (Inorder) both visit Node then Right: 1, 2, 3, 4.

[HI] हर नोड का लेफ्ट खाली होने के कारण N-L-R (प्रीऑर्डर) और L-N-R (इनऑर्डर) दोनों 1, 2, 3, 4 देते हैं।

Q11. What is the time complexity of iterative Preorder Traversal on a binary tree with n nodes?

(n नोड्स वाले बाइनरी ट्री पर इटरेटिव प्रीऑर्डर ट्रैवर्सल की समय जटिलता क्या है?)

(A) O(n)

(B) O(n log n)

(C) O(log n)

(D) O(n^2)

Correct Answer: (A)

[EN] Every node is pushed onto and popped from the stack exactly once, yielding O(n) total operations.

[HI] प्रत्येक नोड स्टैक में ठीक एक बार पुश और एक बार पॉप होता है, अतः कुल समय O(n) है।

Q12. In a directory/file tree listing where every folder name prints before the files inside it, which traversal is being executed?

(किसी फ़ोल्डर/डायरेक्टरी संरचना में प्रत्येक फ़ोल्डर का नाम उसके अंदर की फाइलों से पहले प्रिंट हो, तो यह कौन सा ट्रैवर्सल है?)

(A) Reverse Level Order

(B) Preorder Traversal (DFS)

(C) Postorder Traversal

(D) Inorder Traversal

Correct Answer: (B)

[EN] Parent directory processed prior to descending into child files/subfolders matches Preorder (Node-before-children).

[HI] पेरेंट को उसके चाइल्ड तत्वों से पहले विज़िट करना प्रीऑर्डर ट्रैवर्सल का उदाहरण है।

Q13. For a Perfect Binary Tree of height 2 with 7 nodes, what is the maximum number of nodes held in the stack simultaneously during iterative Preorder?

(ऊंचाई 2 (7 नोड्स) वाले परफेक्ट बाइनरी ट्री में इटरेटिव प्रीऑर्डर के दौरान स्टैक में एक साथ अधिकतम कितने नोड्स हो सकते हैं?)

(A) 3

(B) 7

(C) 2

(D) 1

Correct Answer: (A)

[EN] At depth 0 pop root (push 2), pop left child (push 2 -> stack holds 3), then leaf pops drop size.

[HI] रूट पॉप कर 2 पुश, फिर लेफ्ट चाइल्ड पॉप कर 2 और पुश करने पर अधिकतम 3 नोड्स (h + 1) स्टैक में रहते हैं।

Q14. Which statement is NOT true about Preorder Traversal?

(प्रीऑर्डर ट्रैवर्सल के बारे में इनमें से कौन सा कथन असत्य (NOT true) है?)

(A) Preorder on an Expression Tree gives Prefix notation

(B) Preorder + Inorder uniquely determine a binary tree with distinct keys

(C) Preorder visits Root before Left and Right subtrees

(D) Preorder Traversal of any BST always outputs elements in sorted ascending order

Correct Answer: (D)

[EN] Inorder (not Preorder!) outputs a BST's keys in sorted ascending order.

[HI] BST को सॉर्टेड क्रम में इनऑर्डर देता है, प्रीऑर्डर नहीं!

Q15. What does `10 5 2 8 20 18 25` represent if the BST root is 10 and keys 5, 20 are its immediate children?

(यदि किसी BST का रूट 10 हो और उसके सीधे चाइल्ड 5 व 20 हों, तो क्रम `10 5 2 8 20 18 25` किस ट्रैवर्सल को दर्शाता है?)

(A) Postorder Traversal

(B) Preorder Traversal

(C) Level Order Traversal

(D) Inorder Traversal

Correct Answer: (B)

[EN] 10 comes first (Root), followed by left subtree (5, 2, 8) and right subtree (20, 18, 25)—matching N-L-R.

[HI] 10 सबसे पहले, फिर पूरा बायां सबट्री (5, 2, 8), फिर दायां सबट्री (20, 18, 25) यह प्रीऑर्डर (N-L-R) है।

Q16. Which sentinel-based method allows O(n) serialization and deserialization of ANY binary tree using Preorder alone?

(अकेले प्रीऑर्डर से किसी भी बाइनरी ट्री के O(n) सीरियलाइजेशन और डीसीरियलाइजेशन हेतु किस तकनीक का उपयोग होता है?)

(A) Omitting leaf nodes from the output

(B) Recording explicit NULL markers (e.g., '#') for empty child pointers in the Preorder output

(C) Recording only node heights

(D) Sorting node keys alphabetically

Correct Answer: (B)

[EN] With NULL markers like [1, 2, #, #, 3, #, #], recursive Preorder knows exactly where every subtree terminates.

[HI] खाली पॉइंटर्स के लिए '#' जैसा NULL चिह्न लिख देने से केवल प्रीऑर्डर द्वारा ही ट्री को दोबारा बनाया जा सकता है।

Q17. Within Binary Tree Traversals: Preorder Traversal (N-L-R), which preorder feature directly maps to: "Node (Root) -> Left -> Right"?

(Binary Tree Traversals: Preorder Traversal (N-L-R) में कौन सा Preorder Feature सीधे "Node (Root) -> Left -> Right" से संबंधित है?)

(A) Visit Order

(B) Expression Tree Result

(C) Primary Structural Use

(D) Iterative Stack Push Order

Correct Answer: (A)

[EN] In Binary Tree Traversals: Preorder Traversal (N-L-R), 'Visit Order' handles 'Node (Root) -> Left -> Right' (Root is always the very first element emitted).

[HI] Binary Tree Traversals: Preorder Traversal (N-L-R) में 'Visit Order' का कार्य/विवरण 'Node (Root) -> Left -> Right' (Root is always the very first element emitted) है।

Q18. Which option accurately describes 'Iterative Stack Push Order' in Binary Tree Traversals: Preorder Traversal (N-L-R)?

(Binary Tree Traversals: Preorder Traversal (N-L-R) के संदर्भ में 'Iterative Stack Push Order' की सही विशेषता कौन सी है?)

(A) Node (Root) -> Left -> Right

(B) Tree Cloning & Folder Hierarchy Listing

(C) Prefix (Polish) Notation

(D) Push Right child first, then Left

Correct Answer: (D)

[EN] 'Iterative Stack Push Order' provides 'Push Right child first, then Left' — key point: LIFO stack guarantees Left pops before Right.

[HI] 'Iterative Stack Push Order' का मुख्य विवरण 'Push Right child first, then Left' है (LIFO stack guarantees Left pops before Right)।

Q19. In Binary Tree Traversals: Preorder Traversal (N-L-R), identify the correct parameter for the specification: "Prefix (Polish) Notation".

(Binary Tree Traversals: Preorder Traversal (N-L-R) में "Prefix (Polish) Notation" विवरण किस विकल्प के लिए सही है?)

(A) Expression Tree Result

(B) Iterative Stack Push Order

(C) Primary Structural Use

(D) Visit Order

Correct Answer: (A)

[EN] 'Expression Tree Result' corresponds to 'Prefix (Polish) Notation' (Parentheses-free operator-first form).

[HI] 'Expression Tree Result' का संबंध 'Prefix (Polish) Notation' (Parentheses-free operator-first form) से है।

Q20. Considering Binary Tree Traversals: Preorder Traversal (N-L-R), what key behavior defines 'Primary Structural Use'?

(Binary Tree Traversals: Preorder Traversal (N-L-R) में 'Primary Structural Use' की मुख्य भूमिका या मान क्या है?)

(A) Tree Cloning & Folder Hierarchy Listing

(B) Prefix (Polish) Notation

(C) Push Right child first, then Left

(D) Node (Root) -> Left -> Right

Correct Answer: (A)

[EN] 'Primary Structural Use' represents 'Tree Cloning & Folder Hierarchy Listing' (Parent created/printed before children).

[HI] 'Primary Structural Use' का अर्थ/मान 'Tree Cloning & Folder Hierarchy Listing' है (Parent created/printed before children)।

Binary Tree Traversals: Preorder Traversal (N-L-R) — Exam FAQs

Q1: Why do we push the right child before the left child in iterative Preorder Traversal?

इटरेटिव प्रीऑर्डर में हम पहले राइट चाइल्ड को स्टैक में क्यों पुश करते हैं?

[EN] Because a stack follows Last-In-First-Out (LIFO). Pushing right first and left second puts the left child on top so it pops and executes before the right subtree.

[HI] क्योंकि स्टैक LIFO नियम पर चलता है। राइट को पहले और लेफ्ट को बाद में पुश करने से लेफ्ट चाइल्ड ऊपर रहता है और पहले बाहर निकलता है।

Q2: Does Preorder + Postorder uniquely identify a general binary tree?

क्या प्रीऑर्डर और पोस्टऑर्डर मिलकर किसी भी बाइनरी ट्री को अद्वितीय रूप से बना सकते हैं?

[EN] No. If a node has only one child, Preorder [A, B] and Postorder [B, A] match both when B is A's left child and when B is A's right child. However, they DO uniquely define a Full (Strict) Binary Tree.

[HI] नहीं। जब किसी नोड का केवल एक चाइल्ड हो तब यह स्पष्ट नहीं हो पाता कि वह बायां है या दायां (जब तक कि ट्री फुल/स्ट्रिक्ट बाइनरी ट्री न हो)।

Q3: How is Preorder used in compilers and expression evaluation?

कंपाइलर और एक्सप्रेशन मूल्यांकन में प्रीऑर्डर का क्या उपयोग है?

[EN] Preorder generates Prefix (Polish) notation from an Abstract Syntax / Expression Tree, which avoids precedence parentheses and simplifies recursive prefix parsing.

[HI] प्रीऑर्डर एक्सप्रेशन ट्री से प्रीफिक्स (Polish) नोटेशन उत्पन्न करता है, जिसमें कोष्ठक लगाने की जरूरत नहीं होती।

Related Posts

  • Loading related posts...

Post a Comment

Search Topic Notes & 20 MCQs (Hindi / English)