Please answer all parts of the question (a) Write an algorithm that reverses the

Question

Please answer all parts of the question

(a) Write an algorithm that reverses the left most node and the right most node in a binary tree. Assume that both left and right subtrees of the root T in the binary tree are not empty, and each node contains left, right, parent and value information. b) Write an algorithm which can sort an array A in increasing order: (i) Assume that all the elements of the array are unique. (ii) The main sorting strategy is as follows: check the elements in the array and reverse A[i] and A[I + 1] if A[i] > A[i + 1]. (iii) Repeat part (ii) until such reversal is no longer required (c) Write a divide-and-conquer algorithm that finds the smallest value in a maxheap.

Explanation / Answer

3 a) Algorithm to reverse left most node an d right most node of a binary tree:

Step 1.Traverse the given binary tree by inorder traversal method and store all the odd node values in an auxillary array .

Step 2. Next reverse the array .

Step 3. Again traverse the tree by inorder method and store the one by one elements of the array into the every odd level traversed node.

The run time complexity of the algorithm is O(n) required by two inorder traversing methods.

3 b) Algorithm to sort an array in increasinf order :

Step 1: Read all the elements in array A[] .
Step 2: Assign a variable i=0
Step 3: And Assign j=i+1
Step 4: If A[i] > A[j] then swap value of A[i] and A[j].
Step 5: Assign j=j+1
Step 6: Repeat the Steps 4 and 5 till j is smaller than n
Step 7: Assign i=i+1
Step 8: Repeat the Steps 3 and 7 till i is smaller than n

3 c) Algorithm to find smallest value of maxheap :

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.