Question

I need question 9-10 answered. Thank you

Question 1 iShow the resulting binary search tree if we are to insert following elements into the tree in given order, [34, 12, 23, 27,31,9,11,45, 20, 37. i) Show the resulting balanced binary search tree if we are to insert following sorted elements into the tree, [9,12,21, 23, 29, 31, 34, 45, 48, 52, 55] iii What is the pre-order traversal of the balanced binary search tree? v) What is the post-order traversal of the balanced binary search tree? v) Assuming post order traversal is a recursive algorithm, write the recurrence relation of this algorithm. What is the time complexity of the post-order traversal? Write a recursive C++function to find the sum of all leaf nodes of the balanced binary search tree. What is the time complexity of the algorithm you implemented in # (vi) If we are to delete 31 of the balanced binary search tree, show the tree after the deletion. write a function/pseudo code with O (N+M) time complexity to merge two balanced binary search trees into a single balanced binary search tree. vi) vii) viii) ix)

Answer 1

`Hey,

Note: Brother in case of any queries, just comment in box I would be very happy to assist all your queries

9)

0023 0012 0045 1 2 000900210029 0052 003400480055

10)

PSEUDOCODE

1) Do inorder traversal of first tree and store the traversal in one temp array arr1[]. This step takes O(m) time.
2) Do inorder traversal of second tree and store the traversal in another temp array arr2[]. This step takes O(n) time.
3) The arrays created in step 1 and 2 are sorted arrays. Merge the two sorted arrays into one array of size m + n. This step takes O(m+n) time.
4) Construct a balanced tree from the merged array using the technique discussed in this post. This step takes O(m+n) time.

Time complexity of this method is O(m+n) This method takes O(m+n) time even if the input BSTs are not balanced.

Kindly revert for any queries

Thanks.