PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम Binary Tree Traversals: Postorder Traversal (L-R-N) (पोस्टऑर्डर ट्रैवर्सल (Left-Right-Node): बॉटम-अप मूल्यांकन) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।
Overview: Postorder Traversal (L-R-N) visits the Left subtree, then the Right subtree, and finally processes the Node itself last. This bottom-up order is essential for safely freeing tree memory without dangling pointers, evaluating Postfix (Reverse Polish) expression trees, and computing subtree heights or disk sizes.
अध्याय सार: पोस्टऑर्डर ट्रैवर्सल (Left-Right-Node) में पहले बायां सबट्री, फिर दायां सबट्री और सबसे अंत में स्वयं रूट नोड को विज़िट किया जाता है। यह बॉटम-अप (Bottom-up) क्रम बिना मेमोरी लीक के ट्री को डिलीट करने, पोस्टफिक्स (Postfix/RPN) एक्सप्रेशन हल करने और सबट्री की ऊंचाई या आकार की गणना करने के लिए अनिवार्य है।
Binary Tree Traversals: Postorder Traversal (L-R-N): Detailed Notes & Architecture (पोस्टऑर्डर ट्रैवर्सल (Left-Right-Node): बॉटम-अप मूल्यांकन)
1. L-R-N Bottom-Up Order & Recursive Mechanics (L-R-N बॉटम-अप क्रम व रिकर्सिव प्रणाली)
[EN] Postorder Traversal enforces the Left -> Right -> Node visiting order, ensuring that every descendant of a node is completely processed before the parent node itself is visited. Consequently, the global root is ALWAYS the very last item printed in Postorder. Recursively, `postorder(left)` and `postorder(right)` finish before `visit(root)` executes, requiring Theta(n) time and O(h) recursion call-stack space.
[HI] पोस्टऑर्डर (Left -> Right -> Node) में किसी पेरेंट नोड को विज़िट करने से पहले उसके दोनों सबट्री पूरी तरह प्रोसेस हो जाते हैं, जिससे मुख्य रूट हमेशा सबसे अंत में प्रिंट होता है। इस बॉटम-अप निष्पादन की समय जटिलता Theta(n) और कॉल-स्टैक स्पेस O(h) होता है।
2. Iterative Postorder: Two-Stack vs Single-Stack Methods (इटरेटिव पोस्टऑर्डर: दो-स्टैक बनाम एक-स्टैक विधि)
[EN] Postorder is the trickiest DFS order to write iteratively because a parent must wait until BOTH left and right subtrees finish. The Two-Stack method runs a modified Preorder (Node -> Right -> Left) using Stack1 and pushes each popped item onto Stack2; popping everything from Stack2 reverses N-R-L into exact L-R-N Postorder (using O(n) space). A Single-Stack method keeps O(h) space by tracking a `lastVisited` pointer to verify whether the right child was already processed before popping the parent.
[HI] पोस्टऑर्डर का इटरेटिव रूप सबसे जटिल होता है क्योंकि पेरेंट को दोनों बच्चों के पूरा होने तक रोकना पड़ता है। दो-स्टैक विधि में स्टैक 1 से उल्टा प्रीऑर्डर (N-R-L) चलाकर तत्व स्टैक 2 में डालते हैं, जिसे पॉप करने पर सही L-R-N क्रम मिलता है। एक-स्टैक विधि में `lastVisited` पॉइंटर से राइट चाइल्ड की स्थिति जांची जाती है।
3. Safe Tree Deletion & Memory Deallocation (सुरक्षित ट्री डिलीशन और मेमोरी मुक्ति)
[EN] When deleting an entire binary tree in C/C++, freeing the parent node before freeing its children loses access to `root->left` and `root->right`, causing immediate memory leaks or undefined dangling-pointer reads. Postorder Traversal solves this cleanly: it deletes and frees the entire left subtree, then the entire right subtree, and only frees the parent pointer last.
[HI] C/C++ में ट्री डिलीट करते समय यदि रूट को पहले `free()` कर दें तो उसके बच्चों के पॉइंटर्स खो जाते हैं और मेमोरी लीक हो जाता है। पोस्टऑर्डर ट्रैवर्सल पहले बाएं व दाएं बच्चों की मेमोरी मुक्त करता है और सबसे अंत में पेरेंट को डिलीट करता है।
4. Postfix Expressions & Bottom-Up Tree Computations (पोस्टफिक्स व्यंजक व बॉटम-अप गणनाएं)
[EN] On an arithmetic Expression Tree, Postorder emits Postfix (Reverse Polish Notation / RPN)—such as `A B + C *`—which CPUs and stack machines evaluate left-to-right in a single pass using an operand stack without parentheses. Similarly, bottom-up tree computations like computing tree height (`1 + max(leftH, rightH)`), checking AVL height balance, counting nodes, or calculating total folder sizes (`du`) strictly follow Postorder logic.
[HI] एक्सप्रेशन ट्री पर पोस्टऑर्डर चलाने से पोस्टफिक्स (Reverse Polish Notation) मिलता है, जिसे कंप्यूटर स्टैक द्वारा बिना कोष्ठक के एक बार में हल कर लेता है। इसके अतिरिक्त ट्री की ऊंचाई निकालना, AVL संतुलन जांचना और डायरेक्टरी का कुल साइज जोड़ना पोस्टऑर्डर आधारित बॉटम-अप कार्य हैं।
Syntax, Formula & Technical Example (Binary Tree Traversals: Postorder Traversal (L-R-N))
// Recursive Postorder & Safe Memory Free (L-R-N)
void postorderRec(Node* root) {
if (root == NULL) return;
postorderRec(root->left);
postorderRec(root->right);
printf("%d ", root->data);
}
void deleteTree(Node* root) {
if (root == NULL) return;
deleteTree(root->left);
deleteTree(root->right);
free(root); // Parent freed strictly LAST
}
Binary Tree Traversals: Postorder Traversal (L-R-N) Quick Reference & Comparison Table
| Postorder Concept | Technical Specification | Key Application |
|---|---|---|
| Visit Sequence | Left Subtree -> Right Subtree -> Node | Global root always appears last in sequence |
| Two-Stack Iterative Idea | Reverse of modified Preorder (N-R-L) | Simple iterative logic using O(n) space |
| Single-Stack Iterative Check | Track lastVisited right-child pointer | Reduces auxiliary space down to O(h) |
| Memory & Expression Role | Safe tree free() & Postfix (RPN) output | Children deleted/evaluated before parent |
Binary Tree Traversals: Postorder Traversal (L-R-N) Top 20 Bilingual MCQs with Answers
Q1. Which node of a non-empty binary tree is ALWAYS visited last in Postorder Traversal?
(किसी गैर-खाली बाइनरी ट्री में पोस्टऑर्डर ट्रैवर्सल के दौरान कौन सा नोड सदैव सबसे अंत में विज़िट होता है?)
(A) The rightmost leaf
(B) The leftmost leaf
(C) The Root of the entire tree
(D) The minimum value node
Correct Answer: (C)
[EN] Because Postorder executes Left -> Right -> Node, the top-level root completes strictly last.
[HI] L-R-N क्रम के कारण मुख्य रूट के दोनों सबट्री पूरे होने के बाद ही रूट अंत में विज़िट होता है।
Q2. Why MUST Postorder Traversal be used when freeing/deleting all nodes of a binary tree in C/C++?
(C/C++ में पूरे बाइनरी ट्री को मेमोरी से डिलीट (Free) करते समय पोस्टऑर्डर ट्रैवर्सल का उपयोग क्यों अनिवार्य है?)
(A) Because Preorder reverses child pointers
(B) Because child nodes must be freed before the parent node to prevent losing child pointers (memory leak)
(C) Because free() only works on leaf nodes
(D) Because Postorder runs in O(1) time
Correct Answer: (B)
[EN] Freeing parent first invalidates root->left and root->right before children can be reached.
[HI] यदि पेरेंट को पहले डिलीट कर दिया जाए तो लेफ्ट और राइट चाइल्ड का पता खो जाएगा जिससे मेमोरी लीक होगी।
Q3. What expression notation does Postorder Traversal generate from an arithmetic Expression Tree?
(अंकगणितीय एक्सप्रेशन ट्री पर पोस्टऑर्डर ट्रैवर्सल चलाने से कौन सी नोटेशन प्राप्त होती है?)
(A) Infix Notation
(B) Prefix (Polish) Notation
(C) Postfix (Reverse Polish Notation / RPN)
(D) Hungarian Notation
Correct Answer: (C)
[EN] Left operand, Right operand, then Operator (L-R-N) directly yields Postfix form.
[HI] पहले लेफ्ट ऑपरेंड, फिर राइट ऑपरेंड और अंत में ऑपरेटर (रूट) आने से पोस्टफिक्स (RPN) बनता है।
Q4. Given Root = 10, Left = 5 (Left = 2, Right = 7), and Right = 15 (Right = 20), what is the Postorder sequence?
(रूट 10, लेफ्ट 5 (लेफ्ट=2, राइट=7) व राइट 15 (राइट=20) वाले ट्री का पोस्टऑर्डर क्रम क्या होगा?)
(A) 2, 7, 20, 5, 15, 10
(B) 10, 5, 2, 7, 15, 20
(C) 2, 5, 7, 10, 15, 20
(D) 2, 7, 5, 20, 15, 10
Correct Answer: (D)
[EN] Left(5)->[2, 7, 5], Right(15)->[20, 15], Root->10 gives 2, 7, 5, 20, 15, 10.
[HI] लेफ्ट सबट्री का [2, 7, 5], राइट सबट्री का [20, 15], और अंत में रूट 10: 2, 7, 5, 20, 15, 10।
Q5. The Two-Stack Iterative Postorder algorithm achieves L-R-N by reversing which traversal order?
(दो-स्टैक वाला इटरेटिव पोस्टऑर्डर एल्गोरिदम किस ट्रैवर्सल क्रम को उल्टा (Reverse) करके L-R-N प्राप्त करता है?)
(A) Modified Preorder: Node -> Right -> Left (N-R-L)
(B) Level Order: Top -> Bottom
(C) Inorder: Left -> Node -> Right
(D) Standard Preorder: Node -> Left -> Right
Correct Answer: (A)
[EN] Reversing N-R-L via Stack2 produces exact L-R-N (Postorder).
[HI] N-R-L क्रम को दूसरे स्टैक से उल्टा करने पर ठीक L-R-N (पोस्टऑर्डर) प्राप्त हो जाता है।
Q6. In the Single-Stack Iterative Postorder algorithm, why is a `lastVisited` pointer needed?
(सिंगल-स्टैक इटरेटिव पोस्टऑर्डर में `lastVisited` पॉइंटर की आवश्यकता क्यों होती है?)
(A) To count total leaf nodes
(B) To distinguish whether we are returning from the right subtree or have not visited it yet
(C) To store the minimum node value
(D) To swap left and right children
Correct Answer: (B)
[EN] When peeking at the stack top, if top->right exists and hasn't been visited yet, we must descend right before popping top.
[HI] स्टैक के शीर्ष नोड को पॉप करने से पहले यह जांचने के लिए कि उसका राइट सबट्री विज़िट हो चुका है या नहीं।
Q7. On an Expression Tree representing `(A + B) * (C - D)`, what is the Postorder traversal?
(`(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: (A)
[EN] Left `(A+B)` -> `A B +`; Right `(C-D)` -> `C D -`; Root `*` last -> `A B + C D - *`.
[HI] लेफ्ट भाग A B +, राइट भाग C D -, और मुख्य ऑपरेटर * सबसे अंत में -> A B + C D - *।
Q8. Which tree calculation relies naturally on Postorder (bottom-up) traversal?
(ट्री की कौन सी गणना स्वाभाविक रूप से पोस्टऑर्डर (बॉटम-अप) ट्रैवर्सल पर आधारित है?)
(A) Copying/cloning a tree top-down
(B) Printing BST keys in sorted order
(C) Finding minimum distance from root via BFS
(D) Computing tree height `1 + max(height(left), height(right))`
Correct Answer: (D)
[EN] A parent node's height depends on already knowing both its left and right subtree heights—classic Postorder.
[HI] किसी नोड की ऊंचाई निकालने से पहले उसके लेफ्ट और राइट दोनों सबट्री की ऊंचाई पता होना जरूरी है (बॉटम-अप)।
Q9. If a Binary Tree has Postorder [D, E, B, F, C, A], which node is definitely the root of the entire tree?
(यदि किसी बाइनरी ट्री का पोस्टऑर्डर क्रम [D, E, B, F, C, A] है, तो पूरे ट्री का रूट नोड निश्चित रूप से कौन सा है?)
(A) A
(B) B
(C) C
(D) D
Correct Answer: (A)
[EN] The final element in any Postorder sequence is always the root of the tree.
[HI] किसी भी पोस्टऑर्डर अनुक्रम का सबसे अंतिम तत्व सदैव ट्री का मुख्य रूट होता है।
Q10. What is the auxiliary space complexity of the Two-Stack Iterative Postorder algorithm for an n-node tree?
(n नोड्स वाले ट्री पर दो-स्टैक इटरेटिव पोस्टऑर्डर एल्गोरिदम की अतिरिक्त स्पेस जटिलता क्या होती है?)
(A) O(n) because Stack2 stores all n nodes before popping
(B) O(log n) always
(C) O(1)
(D) O(n^2)
Correct Answer: (A)
[EN] Because every visited node sits inside Stack2 until the end, space is Theta(n) even on balanced trees.
[HI] दूसरे स्टैक में सभी n नोड्स जमा होते हैं, इसलिए संतुलित ट्री पर भी स्पेस जटिलता O(n) होती है।
Q11. Which pair of traversals allows unique reconstruction of ANY binary tree with distinct node keys?
(भिन्न कुंजियों वाले किसी भी बाइनरी ट्री का अद्वितीय पुनर्निर्माण किन दो ट्रैवर्सल के जोड़े से संभव है?)
(A) Postorder and Level Order
(B) Postorder and Preorder
(C) Postorder and Inorder
(D) Postorder alone
Correct Answer: (C)
[EN] Postorder identifies the subtree root (last item), and Inorder splits left vs right subtrees around that root.
[HI] पोस्टऑर्डर से रूट (अंतिम तत्व) मिलता है और इनऑर्डर उसे बाएं व दाएं सबट्री में विभाजित करता है।
Q12. In a directory tree where each folder's total disk usage equals its own files plus the sum of its subfolders, which traversal computes total size?
(यदि किसी डायरेक्टरी ट्री में हर फ़ोल्डर का कुल साइज उसके सबफ़ोल्डर्स के योग के बाद निकलता है, तो कौन सा ट्रैवर्सल उपयोग होता है?)
(A) Breadth-First Search
(B) Inorder Traversal
(C) Postorder Traversal
(D) Preorder Traversal
Correct Answer: (C)
[EN] Subfolder sizes must be aggregated bottom-up before adding them into the parent folder's total.
[HI] सबफ़ोल्डर्स का साइज पहले जुड़ने के बाद ही पेरेंट फ़ोल्डर का कुल साइज निकलता है, जो पोस्टऑर्डर है।
Q13. For a Binary Search Tree whose keys are 20, 10, 30, 5, 15, 25, 35 (Perfect BST rooted at 20), what is the Postorder traversal?
(20 रूट वाले परफेक्ट BST (10, 30 के साथ 5, 15, 25, 35 चाइल्ड) का पोस्टऑर्डर ट्रैवर्सल क्या होगा?)
(A) 5, 10, 15, 20, 25, 30, 35
(B) 5, 15, 10, 25, 35, 30, 20
(C) 5, 15, 25, 35, 10, 30, 20
(D) 20, 10, 5, 15, 30, 25, 35
Correct Answer: (B)
[EN] Left subtree [5, 15, 10], Right subtree [25, 35, 30], Root 20 at the very end.
[HI] बायां सबट्री [5, 15, 10], दायां सबट्री [25, 35, 30] और अंत में रूट 20 आएगा।
Q14. Which statement is NOT true about Postorder Traversal?
(पोस्टऑर्डर ट्रैवर्सल के बारे में इनमें से कौन सा कथन असत्य (NOT true) है?)
(A) Postorder of a single-node tree prints that node
(B) Postorder visits the root before visiting either of its children
(C) Postorder evaluates Postfix expression trees cleanly
(D) Postorder takes Theta(n) time on an n-node tree
Correct Answer: (B)
[EN] Root is visited AFTER both children in Postorder (Node is last in L-R-N), not before.
[HI] पोस्टऑर्डर में रूट दोनों बच्चों के बाद सबसे अंत में विज़िट होता है, पहले नहीं।
Q15. What does recursive Postorder return as its first printed item on ANY non-empty binary tree?
(किसी भी गैर-खाली बाइनरी ट्री पर रिकर्सिव पोस्टऑर्डर सबसे पहले किस प्रकार का नोड प्रिंट करता है?)
(A) Always the root's immediate right child
(B) Always the global root
(C) Always the maximum value node
(D) Always a leaf node (specifically the leftmost bottom-most node)
Correct Answer: (D)
[EN] Recursion descends Left first (and Right if Left is NULL) until hitting a node with zero children—a leaf.
[HI] पोस्टऑर्डर तब तक नीचे उतरता है जब तक कोई लीफ नोड न मिले, अतः सबसे पहले एक लीफ नोड ही प्रिंट होता है।
Q16. Given Preorder [1, 2, 4, 5, 3] and Inorder [4, 2, 5, 1, 3], what is the Postorder sequence?
(यदि किसी बाइनरी ट्री का प्रीऑर्डर [1, 2, 4, 5, 3] और इनऑर्डर [4, 2, 5, 1, 3] है, तो उसका पोस्टऑर्डर क्रम क्या होगा?)
(A) 4, 2, 5, 3, 1
(B) 4, 5, 2, 3, 1
(C) 3, 5, 4, 2, 1
(D) 5, 4, 2, 3, 1
Correct Answer: (B)
[EN] Root=1, Left=[4,2,5] rooted at 2 (Post: 4,5,2), Right=[3], so Postorder = 4, 5, 2, 3, 1.
[HI] रूट 1, लेफ्ट सबट्री (रूट 2, चाइल्ड 4,5 -> 4,5,2) व राइट 3 -> कुल पोस्टऑर्डर 4, 5, 2, 3, 1।
Q17. Within Binary Tree Traversals: Postorder Traversal (L-R-N), which postorder concept directly maps to: "Left Subtree -> Right Subtree -> Node"?
(Binary Tree Traversals: Postorder Traversal (L-R-N) में कौन सा Postorder Concept सीधे "Left Subtree -> Right Subtree -> Node" से संबंधित है?)
(A) Visit Sequence
(B) Two-Stack Iterative Idea
(C) Single-Stack Iterative Check
(D) Memory & Expression Role
Correct Answer: (A)
[EN] In Binary Tree Traversals: Postorder Traversal (L-R-N), 'Visit Sequence' handles 'Left Subtree -> Right Subtree -> Node' (Global root always appears last in sequence).
[HI] Binary Tree Traversals: Postorder Traversal (L-R-N) में 'Visit Sequence' का कार्य/विवरण 'Left Subtree -> Right Subtree -> Node' (Global root always appears last in sequence) है।
Q18. Which option accurately describes 'Two-Stack Iterative Idea' in Binary Tree Traversals: Postorder Traversal (L-R-N)?
(Binary Tree Traversals: Postorder Traversal (L-R-N) के संदर्भ में 'Two-Stack Iterative Idea' की सही विशेषता कौन सी है?)
(A) Reverse of modified Preorder (N-R-L)
(B) Safe tree free() & Postfix (RPN) output
(C) Left Subtree -> Right Subtree -> Node
(D) Track lastVisited right-child pointer
Correct Answer: (A)
[EN] 'Two-Stack Iterative Idea' provides 'Reverse of modified Preorder (N-R-L)' — key point: Simple iterative logic using O(n) space.
[HI] 'Two-Stack Iterative Idea' का मुख्य विवरण 'Reverse of modified Preorder (N-R-L)' है (Simple iterative logic using O(n) space)।
Q19. In Binary Tree Traversals: Postorder Traversal (L-R-N), identify the correct parameter for the specification: "Track lastVisited right-child pointer".
(Binary Tree Traversals: Postorder Traversal (L-R-N) में "Track lastVisited right-child pointer" विवरण किस विकल्प के लिए सही है?)
(A) Visit Sequence
(B) Two-Stack Iterative Idea
(C) Single-Stack Iterative Check
(D) Memory & Expression Role
Correct Answer: (C)
[EN] 'Single-Stack Iterative Check' corresponds to 'Track lastVisited right-child pointer' (Reduces auxiliary space down to O(h)).
[HI] 'Single-Stack Iterative Check' का संबंध 'Track lastVisited right-child pointer' (Reduces auxiliary space down to O(h)) से है।
Q20. Considering Binary Tree Traversals: Postorder Traversal (L-R-N), what key behavior defines 'Memory & Expression Role'?
(Binary Tree Traversals: Postorder Traversal (L-R-N) में 'Memory & Expression Role' की मुख्य भूमिका या मान क्या है?)
(A) Track lastVisited right-child pointer
(B) Reverse of modified Preorder (N-R-L)
(C) Left Subtree -> Right Subtree -> Node
(D) Safe tree free() & Postfix (RPN) output
Correct Answer: (D)
[EN] 'Memory & Expression Role' represents 'Safe tree free() & Postfix (RPN) output' (Children deleted/evaluated before parent).
[HI] 'Memory & Expression Role' का अर्थ/मान 'Safe tree free() & Postfix (RPN) output' है (Children deleted/evaluated before parent)।
Binary Tree Traversals: Postorder Traversal (L-R-N) — Exam FAQs
Q1: Why is Iterative Postorder harder to implement than Iterative Preorder?
इटरेटिव पोस्टऑर्डर लिखना इटरेटिव प्रीऑर्डर की तुलना में कठिन क्यों होता है?
[EN] In Preorder you process a node immediately on first sight and discard it, whereas in Postorder a parent stays on the stack twice—waiting for its left subtree and then waiting for its right subtree before finally being processed.
[HI] प्रीऑर्डर में नोड को पहली बार देखते ही प्रिंट कर दिया जाता है, जबकि पोस्टऑर्डर में पेरेंट नोड को बाएं और दाएं दोनों सबट्री पूरे होने तक स्टैक पर रोके रखना पड़ता है।
Q2: Why is Postfix notation (from Postorder) preferred by stack calculators over Infix?
स्टैक कैलकुलेटर इनफिक्स की बजाय पोस्टऑर्डर से मिलने वाले पोस्टफिक्स (RPN) को क्यों पसंद करते हैं?
[EN] Postfix completely eliminates parentheses and operator-precedence rules: operators appear right after their operands, letting a stack machine evaluate any formula in one O(n) pass.
[HI] पोस्टफिक्स में कोष्ठक और BODMAS/प्राथमिकता नियमों की उलझन नहीं होती; एक साधारण स्टैक से बाएं से दाएं एक ही पास में सटीक मान निकल आता है।
Q3: Can Postorder Traversal of a BST ever be sorted?
क्या किसी BST का पोस्टऑर्डर ट्रैवर्सल कभी सॉर्टेड हो सकता है?
[EN] Yes, in a degenerate edge case: a strictly Left-Skewed BST (e.g., 30 -> 20 -> 10) prints 10, 20, 30 in Postorder! For general BSTs, however, Postorder is NOT sorted.
[HI] केवल एक विशेष स्थिति (पूरी तरह लेफ्ट-स्क्यूड BST जैसे 30->20->10) में पोस्टऑर्डर 10, 20, 30 सॉर्टेड आ सकता है, सामान्य BST में नहीं।
Post a Comment
Post a Comment