Input Format for Custom Testing Sample Case 0 Sample Input O STDIN FUNCTION 3) the size of...
Paytm technical mcq question, verified with a worked answer. Free to practise - no sign-up.
Input Format for Custom Testing Sample Case 0 Sample Input O STDIN FUNCTION 3) > the size of transaction[], n =5 5 > transaction = [5, 3, -4, -10, -3] 3 -4 -10 -3 Sample Output 0 4 Explanation The optimal solution uses transactions 1, 2, 3, and 5 with values 5, 3, -4, and -3. --- [PAGE/IMAGE BREAK] --- QQ) Inorder and Preorder Pick ONE option Given an inorder and preorder traversal of a tree, . find its postorder traversal. ©) 19, 6, 4, 2, 3, 7,10, 5, 1, 8] Inorder: [9, 2, 4, 6, 8, 7, 3, 1, 5, 10] Preorder: [8, 2, 9, 6, 4, 1, 3, 7, 5, 10] (©) None of the above Clear Selection - A) 19,4, 6, 2.7, 3,10, 5,1, 8] - B) ®.4,6,2,3,7,10,5,1,8]
Show answer & explanation
The postorder traversal is derived by recursively identifying the root from the preorder list and splitting the inorder list into left and right subtrees. The root is always visited last in postorder.
Step-by-step Derivation:
Step 1: Preorder [8, 2, 9, 6, 4, 1, 3, 7, 5, 10], Inorder [9, 2, 4, 6, 8, 7, 3, 1, 5, 10]. Root is 8.
Step 2: Split Inorder by 8: Left = [9, 2, 4, 6], Right = [7, 3, 1, 5, 10].
Step 3: Process Left Subtree (Preorder: [2, 9, 6, 4], Inorder: [9, 2, 4, 6]). Root is 2.
- Split Inorder by 2: Left = [9], Right = [4, 6].
- Left [9] is a leaf. Postorder: 9.
- Right [4, 6] (Preorder: [6, 4], Inorder: [4, 6]). Root is 6. Split Inorder: Left = [4], Right = []. Postorder: 4, 6.
- Left subtree postorder: 9, 4, 6, 2.
Step 4: Process Right Subtree (Preorder: [1, 3, 7, 5, 10], Inorder: [7, 3, 1, 5, 10]). Root is 1. - Split Inorder by 1: Left = [7, 3], Right = [5, 10].
- Left [7, 3] (Preorder: [3, 7], Inorder: [7, 3]). Root is 3. Split Inorder: Left = [7], Right = []. Postorder: 7, 3.
- Right [5, 10] (Preorder: [5, 10], Inorder: [5, 10]). Root is 5. Split Inorder: Left = [], Right = [10]. Postorder: 10, 5.
- Right subtree postorder: 7, 3, 10, 5, 1.
Step 5: Combine results (Left, Right, Root): 9, 4, 6, 2, 7, 3, 10, 5, 1, 8. Matching this sequence to the options, Option B contains the correct sequence (despite the OCR noise '®').