Please help me answer this question: ----Here is an example below from another a

Question

Please help me answer this question:

----Here is an example below from another alike question that may help you solve the above question. Please don't spam wrong or incomplete answer:----

Draw the recursion tree when n = 8, where n represents the length of the array, for the following recursive method: int sum (int[ array, int first, int last) if (first = last) return array[firstl; int mid = (first + last) / 2; return sum (array, first, mid) sum (array, mid 1, last) Determine a formula that counts the numbers of nodes in the recursion tree . What is the Big- for execution time? Determine a formula that expresses the height of the tree. What is the Big-? for memory? Write an iterative solution for this same problem and compare its efficiency with this . recursive solution.

Explanation / Answer

// Recursion function to calculate number of Nodes in a Tree
int num_of_nodes(Node root){
if (root == null) return 0;
return 1 + num_of_nodes(root->left) + num_of_nodes(root->right);
}

Time Complexity

The Recursion function can be represented as
T(n) = T(k) + T(n-k-1) + 1
where k is number of nodes on one side of root and (n-k-1) on other side;

Let us analysis for Skew Tree for simplicity

T(n) = T(0) + T(n-1) + 1
T(n) = 2*T(0) + T(n-2) + 2
.
.
.
T(n) = n*T(0) + n

T(0) = 1 (Base case)
therefore T(n) = 2*n
T(n) = (n)

// Recursion function to calculate the height of the Tree
int height(Node root){
if (root == null) return 0;
int l_h = height(root->left);
int r_h = height(root->right);
return 1 + max(l_h,r_h);
}

Time Complexity

The Recursion function can be represented as
T(n) = T(k) + T(n-k-1) + 1
where k is number of nodes on one side of root and (n-k-1) on other side;

Let us analysis for Skew Tree for simplicity

T(n) = T(0) + T(n-1) + 1
T(n) = 2*T(0) + T(n-2) + 2
.
.
.
T(n) = n*T(0) + n

T(0) = 1 (Base case)
therefore T(n) = 2*n
T(n) = (n)

Iterative Method to calculate Height of a Tree

int height(Node root){
if (root == null) return 0;
queue<Node> q;
q.push(root);
int h = 0;
while (true){
if (q.size() == 0)
return h;
h += 1;
int temp = q.size();
while (temp > 0){
Node n = q.pop();
if (n->left != null)
q.push(n->left);
if (n->right != null)
q.push(n->right);
temp -= 1;
}
}
return height;
}

int size(Node root){
if (root == null) return 0;
int size = 1;
stack<Node> s;
s.add(root);
while (s.isEmpty() == false){
Node temp = s.pop();
if (n->left != null){
s.push(n->left);
size += 1;
}
if (n->right != null){
s.push(n->right);
size += 1;
}
}
return size;
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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