1) Write in pseudocode an algorithm that receives as input the root of a tree an
ID: 3936873 • Letter: 1
Question
1) Write in pseudocode an algorithm that receives as input the root of a tree and it returns true if the tree is a proper binary tree (i.e. each internal node has 2 children) and false otherwise. Assume that r.children is the number of children of a node r.
For example, for the tree below with root A the algorithm must return the value true, and for the tree with root B it must return the value false.
1) Compute the time complexity of the above algorithm in the worst case as a function of the number n of nodes and give its order. Explain what the worst case for the algorithm is and how you computed the time complexity.
Explanation / Answer
program how to find
struct node* search(int data){
struct node *current = root;
printf("visiting elements:");
while(current ->data !=data) {
if(current != NULL) {
printf("%d ", current->data);
if (current->data > data) {
current = current ->leftChild;
}
else {
current = current ->rightChild;
}
if( current == NULL) {
return NULL;
}
}
}
return current;
}
BASICS OPERATION :
Search
Inset
Pre-order Traversal
In order Traversal
Post order Traversal
worst case : Worst case can be calculated by O(n)
time complexity of algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. the time complexity of an qlgorithm is commonly expressed using big O notation, which suppress multiplicative constants and lower order terms
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.