I need some help with the following problem. We've touched on scanning tree algorithms a little bit, but not to this extent. My textbook has been useless so far. Can somebody help me with the answers to this?

Answer the following:

template <typename T>
int treeFunc(tnode<T> *t)
{ int n = 0, left, right;

if (t != NULL)
{ if (t->left != NULL)
n++;
if (t->right != NULL)
n++;


left = treeFunc(t->left);
right = treeFunc(t->right);
return n + left + right;
}
else
return 0;
}


What tree scanning algorithm is used above?

(i) preorder left
(ii) inorder left
(iii) postorder left
(iv) inorder right

Any other scanning algorithm could be used to implement the above code?
(v) True
(vi) False

Recommended Answers

All 2 Replies

I need some help with the following problem. We've touched on scanning tree algorithms a little bit, but not to this extent. My textbook has been useless so far. Can somebody help me with the answers to this?

Answer the following:

template <typename T>
int treeFunc(tnode<T> *t)
{ int n = 0, left, right;

if (t != NULL)
{ if (t->left != NULL)
n++;
if (t->right != NULL)
n++;


left = treeFunc(t->left);
right = treeFunc(t->right);
return n + left + right;
}
else
return 0;
}


What tree scanning algorithm is used above?

(i) preorder left
(ii) inorder left
(iii) postorder left
(iv) inorder right

Any other scanning algorithm could be used to implement the above code?
(v) True
(vi) False

I don't need anyone to actually give me the answers, I just need to know how I figure this one out. I can't seem to find out any information on this. Thanks.

Depth first searches are easy to classify. All you need to do is break down the algorithm into recursive calls and actual work done on the downstream, then use the ordering to classify the algorithm. Here's your function without all of the fluff:

if (t->left != NULL)
  n++;
if (t->right != NULL)
  n++;

left = treeFunc(t->left);
right = treeFunc(t->right);

The work is done first, so it's preorder.

>Any other scanning algorithm could be used to implement the above code?
It's trivial to write the code to test this, and changing the function to use another "scanning algorithm" is even easier. Give it a shot and see. Alternatively, you could work through each scanning algorithm on a sample tree and see what the results are.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.