The following is a pseudocode algorithm for iterative binary tree inorder traversal. elemType* stack; //a stack...

Transcribed Image Text:

The following is a pseudocode algorithm for iterative binary tree inorder traversal. elemType* stack; //a stack to store nodes current root; //start traversing the binary tree at the root node while (current is not NULL or stack is nonempty) if (current is not NULL) { push current into the statck; current = current->llink; } else { pop stack into current; visit current; current current->rlink; // visit the node // move to the right child } 1) A full node is a node with two children. Modify the above code (you can directly annotate it) to compute the number of full nodes in a binary tree. 2) Write a recursive implementation for the same function. What is the time complexity and why? The following is a pseudocode algorithm for iterative binary tree inorder traversal. elemType* stack; //a stack to store nodes current root; //start traversing the binary tree at the root node while (current is not NULL or stack is nonempty) if (current is not NULL) { push current into the statck; current = current->llink; } else { pop stack into current; visit current; current current->rlink; // visit the node // move to the right child } 1) A full node is a node with two children. Modify the above code (you can directly annotate it) to compute the number of full nodes in a binary tree. 2) Write a recursive implementation for the same function. What is the time complexity and why?

Answer rating: 100% (QA)

1 2 The time complexity of recursive f... View the full answer