As, it is the HomeworkLib policy to just answer one question in an answer.Hence, I have posted only answer to your first question and the rest you'll have to post as another question.Thankyou
Algorithm:
This is the algorithm to calculate the number of levels in the binary tree using the divide and conquer rule.
int numLevel(Node *roots)
{
if(roots == NULL) return
Initialising a Queue
Adding roots to QUEUE
Add a Dummy Node(NULL pointer) to Queue
num_of_levels = 1
while(QUEUE is not enmpty)
{
Dequeuing a node from Queue and assigning it to the root
if(roots == NULL and QUEUE is not empyy)
{
Adding NULL pointer(dummy node) to QUEUE
num_of_levels ++
}
if(roots->lt)
Adding roots->left element to QUEUE
if(roots->rt)
Adding roots->right element to QUEUE
}
return num_of_levels
}
Design a divide-and-conquer algorithm for computing the number of levels in a binary tree. In particular,...
Design a divide-and-conquer algorithm in pseudocode for computing the number of levels in a binary tree. In particular, your algorithm must return 0 and 1 for the empty and single-node trees, respectively. What is the time efficiency class of your algorithm?
1. Design and write a Divide& Conquer algorithm that, given an array A of n distinct integers which is already sorted into ascending order, will find if there is some i such that Ali] in worst-case 0(log n) time.
Suppose the following is a divide-and-conquer algorithm for some problem. "Make the input of size n into 3 subproblems of sizes n/2 , n/4 , n/8 , respectively with O(n) time; Recursively call on these subproblems; and then combine the results in O(n) time. The recursive call returns when the problems become of size 1 and the time in this case is constant." (a) Let T(n) denote the worst-case running time of this approach on the problem of size n....
3. [5 marks] Suppose T is a binary tree that stores an integer key value in each node. Assume the following notation/operations on a binary tree. » the key T.key is the root node's integer key value . the left child T.left is T's left subtree, which is possibly an empty tree (or null) the right child T.right is T's right subtree, which is possibly an empty tree (or null) (a) Write an efficient algorithm FINDMAxPrODuCT(T) in pseudocode that returns...
For a 2-3 tree containing real numbers, design an algorithm for computing the range (i.e., the difference between the largest and smallest numbers in the tree) and determine its worst-case efficiency.
1. What is the worst case time complexity of insertion into a binary search tree with n elements? You should use the most accurate asymptotic notation for your answer. 2. A binary search tree is given in the following. Draw the resulting binary search tree (to the right of the given tree) after deleting the node with key value 8. 10 3. You have a sorted array B with n elements, where n is very large. Array C is obtained...
Trees and Heaps 1. Show that the maximum number of nodes in a binary tree of height h is 2h+1 − 1. 2. A full node is a node with two children. Prove that the number of full nodes plus one is equal to the number of leaves in a nonempty binary tree. 3. What is the minimum number of nodes in an AVL tree of height 15? 4. Show the result of inserting 14, 12, 18, 20, 27, 16,...
1. Please write a Divide-and-Conquer Java algorithm solving the following problem: Given an "almost sorted" array of distinct integers, and an integer x, return the index of x in the array. If the element x is not present in the array, return -1. "Almost sorted" means the following. Assume you had a sorted array A[0…N], and then split it into two pieces A[0…M] and A[M+1…N], and move the second piece upfront to get the following: A[M+1]…A[N]A[0]…A[M]. Thus, the "almost sorted"...
Design a recursive algorithm that determines whether the number of leaf nodes of a Binary Search Tree (BST) is even or odd. An empty tree has an even number of leaves. A tree consisting of just a root has an odd number of leaves. Your function should return true for an even number of leaves, and false for an odd number of leaves. Analyze the execution time of your algorithm. Giving only the execution time without explanation will not be...
Design a recursive algorithm that determines whether the number of leaf nodes of a Binary Search Tree (BST) is even or odd. An empty tree has an even number of leaves. A tree consisting of just a root has an odd number of leaves. Your function should return true for an even number of leaves, and false for an odd number of leaves. Analyze the execution time of your algorithm. Giving only the execution time without explanation will not be...