PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम Binary Tree Depth-First Traversals: Inorder Traversal (L-N-R) (इनऑर्डर ट्रैवर्सल (Left-Node-Right): रिकर्सिव और इटरेटिव विधि) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।
Overview: Inorder Traversal (L-N-R) is a Depth-First Search algorithm that visits a node's left subtree, processes the node itself, and then visits its right subtree. It outputs Binary Search Tree (BST) keys in sorted ascending order and runs in O(n) time using O(h) recursion stack space or O(1) space via Morris Traversal.
अध्याय सार: इनऑर्डर ट्रैवर्सल (Left-Node-Right) एक डेप्थ-फर्स्ट सर्च (DFS) विधि है जिसमें पहले बायां सबट्री, फिर स्वयं रूट नोड और अंत में दायां सबट्री विज़िट किया जाता है। किसी बाइनरी सर्च ट्री (BST) का इनऑर्डर ट्रैवर्सल सदैव आरोही (Sorted Ascending) क्रम में परिणाम देता है तथा इसकी समय जटिलता O(n) होती है।
Binary Tree Depth-First Traversals: Inorder Traversal (L-N-R): Detailed Notes & Architecture (इनऑर्डर ट्रैवर्सल (Left-Node-Right): रिकर्सिव और इटरेटिव विधि)
1. L-N-R Rule & Recursive Execution Flow (L-N-R नियम एवं रिकर्सिव निष्पादन क्रम)
[EN] Inorder Traversal follows the strict Left -> Node -> Right sequence at every node in the tree. Starting at root, recursion plunges all the way down left pointers until reaching a NULL child, returns to print/process that node, and only then explores its right subtree. Every node is visited once and every edge is traversed twice, fixing time complexity at Theta(n), while the implicit call stack consumes O(h) auxiliary space (O(log n) balanced, O(n) skewed).
[HI] इनऑर्डर ट्रैवर्सल प्रत्येक नोड पर पहले लेफ्ट सबट्री, फिर नोड, और अंत में राइट सबट्री के क्रम का पालन करता है। रिकर्सन बाएं पॉइंटर्स के सहारे तब तक नीचे जाता है जब तक NULL न मिले, फिर नोड को प्रोसेस कर दाएं सबट्री में जाता है। प्रत्येक नोड एक बार प्रोसेस होने से समय जटिलता O(n) व स्टैक स्पेस O(h) रहता है।
2. Iterative Stack-Based Inorder Simulation (एक्सप्लिसिट स्टैक से इटरेटिव इनऑर्डर विधि)
[EN] To eliminate recursion overhead and avoid potential system call-stack limits, iterative Inorder maintains an explicit stack and a current pointer initialized to root. While current is non-NULL or the stack is non-empty: keep pushing current onto the stack and advancing current = current->left; once NULL is reached, pop the top node, visit its data, and shift current = popped->right. This mirrors the exact call-stack frames manually in O(h) space.
[HI] रिकर्सन हटाने के लिए इटरेटिव विधि में एक एक्सप्लिसिट स्टैक और curr पॉइंटर उपयोग होता है। जब तक curr नॉन-NULL हो, उसे स्टैक में पुश करके curr = curr->left करते जाते हैं। NULL मिलने पर स्टैक से नोड पॉप कर प्रिंट करते हैं और curr को पॉप किए गए नोड के right चाइल्ड पर सेट कर देते हैं।
3. Morris Traversal: O(1) Space Inorder (मॉरिस ट्रैवर्सल: O(1) अतिरिक्त स्पेस में इनऑर्डर)
[EN] Morris Inorder Traversal achieves O(n) time with O(1) auxiliary space—neither recursion nor an explicit stack—by temporarily forming threaded links. For a node with a non-NULL left child, it locates its Inorder Predecessor (rightmost node of its left subtree): if predecessor->right is NULL, it temporarily points it back to current and moves left; upon returning via that thread, it restores predecessor->right = NULL, prints current, and moves right.
[HI] मॉरिस इनऑर्डर ट्रैवर्सल बिना स्टैक और बिना रिकर्सन के O(1) स्पेस में चलता है। इसमें किसी नोड के लेफ्ट सबट्री के सबसे दाहिने नोड (Inorder Predecessor) का राइट पॉइंटर अस्थायी रूप से वर्तमान नोड से जोड़ (Thread) दिया जाता है, और नोड प्रिंट होने के बाद उस लिंक को वापस NULL करके ट्री का मूल रूप बहाल कर दिया जाता है।
4. Sorted Output on BST & Infix Expressions (BST में सॉर्टेड आउटपुट व इनफिक्स व्यंजक)
[EN] The hallmark property of Inorder Traversal is that when executed on any valid Binary Search Tree (Left < Root < Right), it prints all keys in sorted non-decreasing order—making it essential for BST validation, finding the k-th smallest key, or flattening a BST into a sorted array. On an Expression Tree, Inorder emits an infix expression (like A + B * C), though parentheses must be added around subexpressions to preserve operator precedence.
[HI] इनऑर्डर ट्रैवर्सल की सबसे प्रमुख विशेषता यह है कि किसी भी BST पर चलाने पर यह सभी कुंजियों को बढ़ते क्रम (Sorted Ascending Order) में प्रिंट करता है। एक्सप्रेशन ट्री पर इनऑर्डर चलाने से इनफिक्स (Infix) व्यंजक मिलता है, हालांकि ऑपरेटर प्राथमिकता बचाने हेतु कोष्ठक लगाने आवश्यक होते हैं।
Syntax, Formula & Technical Example (Binary Tree Depth-First Traversals: Inorder Traversal (L-N-R))
// Recursive and Iterative Inorder Traversal (L-N-R)
void inorderRec(Node* root) {
if (root == NULL) return;
inorderRec(root->left);
printf("%d ", root->data);
inorderRec(root->right);
}
void inorderIter(Node* root) {
Stack s; Node* curr = root;
while (curr != NULL || !isEmpty(&s)) {
while (curr != NULL) { push(&s, curr); curr = curr->left; }
curr = pop(&s); printf("%d ", curr->data); curr = curr->right;
}
}
Binary Tree Depth-First Traversals: Inorder Traversal (L-N-R) Quick Reference & Comparison Table
| Inorder Aspect | Technical Value / Behavior | Exam Note |
|---|---|---|
| Visit Sequence | Left Subtree -> Node -> Right Subtree | Acronym L-N-R; root sits between subtrees |
| BST Result Order | Strictly non-decreasing (sorted ascending) | Used to extract sorted keys or find k-th smallest |
| Morris Space Complexity | O(1) auxiliary space (no stack) | Temporarily threads predecessor->right to curr |
| Expression Tree Output | Infix notation (parentheses needed) | E.g., (A + B) * C from operator-interior tree |
Binary Tree Depth-First Traversals: Inorder Traversal (L-N-R) Top 20 Bilingual MCQs with Answers
Q1. What is the exact node processing sequence in Inorder Traversal?
(इनऑर्डर ट्रैवर्सल में नोड्स को विज़िट करने का सटीक क्रम क्या है?)
(A) Right subtree, then Root, then Left subtree
(B) Left subtree, then Root (Node), then Right subtree
(C) Left subtree, then Right subtree, then Root
(D) Root, then Left subtree, then Right subtree
Correct Answer: (B)
[EN] Inorder follows L-N-R: recursively process left child, visit current node, then process right child.
[HI] इनऑर्डर L-N-R क्रम अपनाता है: पहले बायां सबट्री, फिर रूट नोड, और फिर दायां सबट्री।
Q2. Which tree traversal of a Binary Search Tree (BST) yields keys in ascending sorted order?
(बाइनरी सर्च ट्री (BST) का कौन सा ट्रैवर्सल कुंजियों को आरोही (Ascending Sorted) क्रम में देता है?)
(A) Postorder Traversal
(B) Inorder Traversal
(C) Preorder Traversal
(D) Level Order Traversal
Correct Answer: (B)
[EN] Because Left < Root < Right holds at every node in a BST, L-N-R prints all elements sorted ascending.
[HI] BST में Left < Root < Right नियम होने से L-N-R (Inorder) ट्रैवर्सल सदैव सॉर्टेड आउटपुट देता है।
Q3. What is the worst-case auxiliary space complexity of recursive Inorder Traversal on an n-node binary tree?
(n नोड्स वाले बाइनरी ट्री पर रिकर्सिव इनऑर्डर ट्रैवर्सल की सबसे खराब स्थिति (Worst-case) में अतिरिक्त स्पेस जटिलता क्या है?)
(A) O(1) always
(B) O(n^2)
(C) O(log n) always
(D) O(n) when the tree is skewed
Correct Answer: (D)
[EN] Auxiliary space equals recursion depth O(h); for a skewed tree, h = n - 1, giving O(n) stack space.
[HI] रिकर्सन स्टैक की गहराई ट्री की ऊंचाई h के बराबर होती है, जो स्क्यूड ट्री में O(n) तक जाती है।
Q4. Which traversal algorithm performs Inorder Traversal in O(n) time and O(1) extra space without recursion or an explicit stack?
(कौन सा एल्गोरिदम बिना रिकर्सन और बिना स्टैक के O(n) समय और O(1) अतिरिक्त स्पेस में इनऑर्डर ट्रैवर्सल करता है?)
(A) Two-Stack Postorder
(B) Morris Traversal (using temporary right threads)
(C) Iterative Deepening DFS
(D) Breadth-First Search
Correct Answer: (B)
[EN] Morris Traversal threads each inorder predecessor's NULL right pointer back to current temporarily, eliminating stack space.
[HI] मॉरिस ट्रैवर्सल प्रीडीसेसर के राइट पॉइंटर को अस्थायी रूप से थ्रेड बनाकर O(1) स्पेस में इनऑर्डर पूरा करता है।
Q5. Consider a binary tree with Root = 10, Left = 5 (having Left = 2, Right = 7), and Right = 15 (having Right = 20). What is its Inorder Traversal?
(यदि रूट 10 हो, उसका लेफ्ट 5 (लेफ्ट=2, राइट=7) व राइट 15 (राइट=20) हो, तो इसका इनऑर्डर ट्रैवर्सल क्या होगा?)
(A) 2, 7, 5, 20, 15, 10
(B) 2, 5, 7, 10, 15, 20
(C) 10, 5, 2, 7, 15, 20
(D) 10, 5, 15, 2, 7, 20
Correct Answer: (B)
[EN] Tracing L-N-R: Left(5)->[2, 5, 7], Root 10, Right(15)->[15, 20], producing 2, 5, 7, 10, 15, 20.
[HI] L-N-R क्रम से बाईं ओर [2, 5, 7], फिर रूट 10, फिर दाईं ओर [15, 20] प्रिंट होगा।
Q6. In iterative Inorder Traversal using a stack, what happens immediately after popping a node curr and printing it?
(स्टैक आधारित इटरेटिव इनऑर्डर ट्रैवर्सल में किसी नोड curr को पॉप और प्रिंट करने के ठीक बाद क्या किया जाता है?)
(A) Terminate the loop
(B) Push curr->left then curr->right
(C) Set curr = curr->left
(D) Set curr = curr->right
Correct Answer: (D)
[EN] Its left subtree was already exhausted before popping, so next we explore curr->right.
[HI] नोड का बायां भाग पहले ही प्रोसेस हो चुका होता है, इसलिए पॉप के बाद curr को curr->right पर बढ़ाते हैं।
Q7. What expression notation is produced by running Inorder Traversal on an arithmetic Expression Tree?
(अंकगणितीय एक्सप्रेशन ट्री पर इनऑर्डर ट्रैवर्सल चलाने से किस प्रकार का व्यंजक प्राप्त होता है?)
(A) Postfix (Reverse Polish) notation
(B) Prefix (Polish) notation
(C) Binary machine opcode
(D) Infix notation (requiring parentheses for precedence)
Correct Answer: (D)
[EN] Operators sit at internal nodes between left and right operands, yielding standard Infix order (L-N-R).
[HI] ऑपरेटर बीच में (N) और ऑपरेंड्स दोनों तरफ (L व R) होने से इनफिक्स व्यंजक प्राप्त होता है।
Q8. To obtain keys of a Binary Search Tree in DESCENDING (reverse) sorted order, which modified DFS order works directly?
(किसी BST की कुंजियों को अवरोही (Descending Sorted) क्रम में पाने के लिए कौन सा ट्रैवर्सल क्रम अपनाया जाता है?)
(A) Postorder: Left -> Right -> Node
(B) Right -> Left -> Node
(C) Preorder: Node -> Left -> Right
(D) Reverse Inorder: Right -> Node -> Left (R-N-L)
Correct Answer: (D)
[EN] Visiting the larger Right subtree first, then Root, then smaller Left subtree yields descending order.
[HI] राइट -> नोड -> लेफ्ट (रिवर्स इनऑर्डर) क्रम में चलने से सबसे बड़ी कुंजियां पहले प्रिंट होती हैं।
Q9. Can Inorder Traversal alone uniquely reconstruct the structure of an arbitrary binary tree?
(क्या केवल इनऑर्डर ट्रैवर्सल के आधार पर किसी बाइनरी ट्री की सटीक संरचना का पुनर्निर्माण किया जा सकता है?)
(A) Yes, for any binary tree
(B) Yes, because the first element is always root
(C) Yes, if node count is odd
(D) No — multiple structurally distinct binary trees can have the same Inorder sequence
Correct Answer: (D)
[EN] For instance, a right-skewed tree A->B and a left-skewed tree B->A both share Inorder [A, B].
[HI] नहीं — एक ही इनऑर्डर क्रम (जैसे [A, B]) वाले कई अलग-अलग ट्री संभव हैं, इसलिए साथ में प्रीऑर्डर या पोस्टऑर्डर चाहिए।
Q10. If a binary tree has 12 nodes, how many times is the base-case `if (root == NULL) return;` executed in recursive Inorder?
(यदि एक बाइनरी ट्री में 12 नोड्स हैं, तो रिकर्सिव इनऑर्डर के दौरान बेस केस `if (root == NULL)` कितनी बार चलेगा?)
(A) 11 times
(B) 24 times
(C) 13 times
(D) 12 times
Correct Answer: (C)
[EN] An n-node binary tree has exactly n + 1 NULL pointers, so the NULL base case triggers 12 + 1 = 13 times.
[HI] n नोड्स वाले ट्री में n + 1 NULL पॉइंटर्स होते हैं, इसलिए 12 + 1 = 13 बार बेस केस चलेगा।
Q11. How can you find the k-th smallest element in a BST most naturally using tree traversal?
(BST में k-वां सबसे छोटा तत्व (k-th smallest element) किस ट्रैवर्सल से सबसे स्वाभाविक रूप से खोजा जाता है?)
(A) Perform Preorder Traversal and pick the k-th leaf
(B) Perform Inorder Traversal with a counter and stop at the k-th visited node
(C) Perform Level Order Traversal and pick index k
(D) Perform Postorder Traversal and stop at k
Correct Answer: (B)
[EN] Because Inorder yields keys in ascending order, the k-th node visited is the k-th smallest key.
[HI] इनऑर्डर ट्रैवर्सल बढ़ते क्रम में चलता है, अतः गिनती रखते हुए k-वां विज़िट किया गया नोड ही k-वां सबसे छोटा होगा।
Q12. In a Binary Tree, what is the 'Inorder Successor' of a node x that has a non-empty right subtree?
(बाइनरी ट्री में यदि किसी नोड x का दायां सबट्री मौजूद हो, तो उसका 'इनऑर्डर सक्सेसर' (Inorder Successor) कौन होगा?)
(A) The root of the entire tree
(B) The rightmost node in x's left subtree
(C) x's immediate parent
(D) The leftmost node in x's right subtree
Correct Answer: (D)
[EN] Right after visiting x in L-N-R, traversal enters x->right and goes all the way left.
[HI] x को प्रिंट करने के बाद इनऑर्डर दाएं सबट्री में सबसे बाएं नोड पर जाता है, वही इसका सक्सेसर होता है।
Q13. What is the time complexity of Inorder Traversal across all n nodes of a binary tree?
(n नोड्स वाले बाइनरी ट्री में इनऑर्डर ट्रैवर्सल की कुल समय जटिलता कितनी होती है?)
(A) Theta(n)
(B) Theta(log n)
(C) Theta(n^2)
(D) Theta(n log n)
Correct Answer: (A)
[EN] By the recursion master equation or pointer counting, each of the n nodes is visited once: Theta(n).
[HI] प्रत्येक नोड और एज निश्चित बार विज़िट होने से इसकी समय जटिलता Theta(n) होती है।
Q14. During Morris Inorder Traversal, which pointer on the Inorder Predecessor is temporarily modified?
(मॉरिस इनऑर्डर ट्रैवर्सल के दौरान इनऑर्डर प्रीडीसेसर (Predecessor) के किस पॉइंटर को अस्थायी रूप से बदला जाता है?)
(A) The predecessor's right pointer (initially NULL)
(B) The root's parent pointer
(C) The successor's data field
(D) The predecessor's left pointer
Correct Answer: (A)
[EN] The inorder predecessor has no right child (NULL), so Morris uses predecessor->right as a return thread.
[HI] इनऑर्डर प्रीडीसेसर का राइट पॉइंटर खाली (NULL) होता है, इसलिए उसी पर अस्थायी थ्रेड बनाया जाता है।
Q15. Which statement is NOT true about Inorder Traversal?
(इनऑर्डर ट्रैवर्सल के विषय में इनमें से कौन सा कथन असत्य (NOT true) है?)
(A) Recursive Inorder has O(h) auxiliary space complexity
(B) In a BST, Inorder traversal visits keys in sorted ascending order
(C) Iterative Inorder uses a LIFO stack
(D) The root of the entire tree is always the first element in the Inorder output
Correct Answer: (D)
[EN] Root is first in Preorder, last in Postorder, and generally somewhere in the middle in Inorder (first only if left subtree is empty).
[HI] रूट हमेशा पहले प्रीऑर्डर में आता है; इनऑर्डर में रूट बाएं और दाएं सबट्री के बीच में आता है।
Q16. Given a binary tree with root A, left child B, and right child C where B has right child D, what is the Inorder sequence?
(रूट A, लेफ्ट चाइल्ड B (जिसका राइट चाइल्ड D है) और राइट चाइल्ड C वाले ट्री का इनऑर्डर क्रम क्या होगा?)
(A) B, D, A, C
(B) D, B, C, A
(C) A, B, D, C
(D) B, A, D, C
Correct Answer: (A)
[EN] For B: left=NULL, node=B, right=D -> [B, D]. Then root A, then right C -> B, D, A, C.
[HI] B का लेफ्ट खाली है इसलिए पहले B, फिर उसका राइट D, फिर रूट A और अंत में C अर्थात B, D, A, C मिलेगा।
Q17. Within Binary Tree Depth-First Traversals: Inorder Traversal (L-N-R), which inorder aspect directly maps to: "Left Subtree -> Node -> Right Subtree"?
(Binary Tree Depth-First Traversals: Inorder Traversal (L-N-R) में कौन सा Inorder Aspect सीधे "Left Subtree -> Node -> Right Subtree" से संबंधित है?)
(A) Morris Space Complexity
(B) BST Result Order
(C) Expression Tree Output
(D) Visit Sequence
Correct Answer: (D)
[EN] In Binary Tree Depth-First Traversals: Inorder Traversal (L-N-R), 'Visit Sequence' handles 'Left Subtree -> Node -> Right Subtree' (Acronym L-N-R; root sits between subtrees).
[HI] Binary Tree Depth-First Traversals: Inorder Traversal (L-N-R) में 'Visit Sequence' का कार्य/विवरण 'Left Subtree -> Node -> Right Subtree' (Acronym L-N-R; root sits between subtrees) है।
Q18. Which option accurately describes 'BST Result Order' in Binary Tree Depth-First Traversals: Inorder Traversal (L-N-R)?
(Binary Tree Depth-First Traversals: Inorder Traversal (L-N-R) के संदर्भ में 'BST Result Order' की सही विशेषता कौन सी है?)
(A) Left Subtree -> Node -> Right Subtree
(B) O(1) auxiliary space (no stack)
(C) Infix notation (parentheses needed)
(D) Strictly non-decreasing (sorted ascending)
Correct Answer: (D)
[EN] 'BST Result Order' provides 'Strictly non-decreasing (sorted ascending)' — key point: Used to extract sorted keys or find k-th smallest.
[HI] 'BST Result Order' का मुख्य विवरण 'Strictly non-decreasing (sorted ascending)' है (Used to extract sorted keys or find k-th smallest)।
Q19. In Binary Tree Depth-First Traversals: Inorder Traversal (L-N-R), identify the correct parameter for the specification: "O(1) auxiliary space (no stack)".
(Binary Tree Depth-First Traversals: Inorder Traversal (L-N-R) में "O(1) auxiliary space (no stack)" विवरण किस विकल्प के लिए सही है?)
(A) Visit Sequence
(B) Expression Tree Output
(C) BST Result Order
(D) Morris Space Complexity
Correct Answer: (D)
[EN] 'Morris Space Complexity' corresponds to 'O(1) auxiliary space (no stack)' (Temporarily threads predecessor->right to curr).
[HI] 'Morris Space Complexity' का संबंध 'O(1) auxiliary space (no stack)' (Temporarily threads predecessor->right to curr) से है।
Q20. Considering Binary Tree Depth-First Traversals: Inorder Traversal (L-N-R), what key behavior defines 'Expression Tree Output'?
(Binary Tree Depth-First Traversals: Inorder Traversal (L-N-R) में 'Expression Tree Output' की मुख्य भूमिका या मान क्या है?)
(A) Strictly non-decreasing (sorted ascending)
(B) O(1) auxiliary space (no stack)
(C) Infix notation (parentheses needed)
(D) Left Subtree -> Node -> Right Subtree
Correct Answer: (C)
[EN] 'Expression Tree Output' represents 'Infix notation (parentheses needed)' (E.g., (A + B) * C from operator-interior tree).
[HI] 'Expression Tree Output' का अर्थ/मान 'Infix notation (parentheses needed)' है (E.g., (A + B) * C from operator-interior tree)।
Binary Tree Depth-First Traversals: Inorder Traversal (L-N-R) — Exam FAQs
Q1: Why does Inorder Traversal produce sorted output only on a BST and not on an arbitrary Binary Tree?
इनऑर्डर ट्रैवर्सल केवल BST पर ही सॉर्टेड आउटपुट क्यों देता है, किसी सामान्य बाइनरी ट्री पर क्यों नहीं?
[EN] Because only a Binary Search Tree enforces the ordering invariant Left < Node < Right at every node, which directly aligns with the Left-Node-Right visit order of Inorder Traversal.
[HI] क्योंकि केवल BST में ही Left < Node < Right नियम का पालन होता है, जो इनऑर्डर के L-N-R विज़िट क्रम से हूबहू मेल खाता है।
Q2: Is Morris Inorder Traversal safe in multi-threaded read-only access?
क्या मल्टी-थ्रेडेड रीड-ओनली वातावरण में मॉरिस इनऑर्डर ट्रैवर्सल सुरक्षित है?
[EN] No. Even though Morris Traversal restores the tree afterward, it temporarily mutates NULL right pointers during execution, making it unsafe for concurrent readers without locks.
[HI] नहीं। भले ही मॉरिस ट्रैवर्सल अंत में ट्री को ठीक कर देता है, पर चलने के दौरान यह अस्थायी रूप से पॉइंटर्स बदलता है इसलिए बिना लॉक के मल्टी-थ्रेडिंग में असुरक्षित है।
Q3: When should I choose Iterative Inorder over Recursive Inorder?
हमें रिकर्सिव की जगह इटरेटिव इनऑर्डर कब चुनना चाहिए?
[EN] Choose Iterative Inorder on very deep or skewed trees (e.g., n > 10^5) where recursion can exhaust the OS thread call stack, or when implementing lazy iterators (`next()`).
[HI] जब ट्री बहुत गहरा या स्क्यूड हो (जहां स्टैक ओवरफ्लो का खतरा हो) या जब हमें एक-एक कर अगला नोड देने वाला इटरेटर (Iterator) बनाना हो।
Post a Comment
Post a Comment