Q2 a) - Easiest: O(n) time and space We do a inorder traversal, and put it in the linked list
- Improved: Rotate right, till theres no left child if theres no left child, go to the right child and rotate O(n) //traversal, rotation O(1) O(1) //space
b) - Easiest : Recursion, find median and continue O(nlogn) Space(logn) //recursion stack
- Improved:
2T(n/2) + o(1) Make a function that will take in a List and n The function will return connect the mid with the left tree and right tree recursively while passing n which is taking the number of elements of the list
Find mid, do a recursive step of building the left and right tree. To build left, Take first n/2 elements and put in function To build right. Take the n- n/2 - 1 elements of the right and put in function
The base case is when n =0 , return value iteself recursive step add(left) , add(mid) , add(right)