### Thread: Iterator Method for Binary Trees in C

1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Jan 2014
Posts
3
Rep Power
0

#### Iterator Method for Binary Trees in C

I've been given the following instruction:

Add a new method to the library that applies a function to every value in the tree. (This is an iterator method for trees.)

Code:
`int bst_char_iterate(bst_char *t, char (*fun)(char item))`
NB: The BST property will only be preserved by this method if the function passed to it is monotonic. A function f is monotonic whenever
x &lt;= y (arrow) f(x) &lt;= f(y).

"Bst_char *t" equating to a pointer to the tree, "*fun" equating to a pointer to a function call and "item" being the value of which the function is called upon.

I've managed to come up with this:

Code:
```int bst_char_iterate(bst_char *t, char (*fun)(char item)) {
assert(t!=NULL);
struct node * p = t-&gt;root;
if (p!=NULL) {
p-&gt;item = fun(p-&gt;item);
p-&gt;left-&gt;item = bst_char_iterate(t,fun(p-&gt;left));
p-&gt;right-&gt;item = bst_char_iterate(t,fun(p-&gt;right));
} else {
return 0;
}
}```
This cannot compile, with quite a few errors (such as "from pointer without a cast").

2. > p->left->item = bst_char_iterate(t,fun(p->left));
> p->right->item = bst_char_iterate(t,fun(p->right));
These should be
bst_char_iterate(p->left,fun);
bst_char_iterate(p->right,fun);
3. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Jan 2014
Posts
3
Rep Power
0
Originally Posted by salem
> p->left->item = bst_char_iterate(t,fun(p->left));
> p->right->item = bst_char_iterate(t,fun(p->right));
These should be
bst_char_iterate(p->left,fun);
bst_char_iterate(p->right,fun);
When I changed it, the following errors came up when attempting to compile:

pfbst_char.c: In function ‘bst_char_iterate’:
pfbst_char.c:388:8: warning: passing argument 1 of ‘bst_char_iterate’ from incompatible pointer type [enabled by default]
bst_char_iterate(p->left,fun);
^
pfbst_char.c:381:5: note: expected ‘struct bst_char *’ but argument is of type ‘struct node *’
int bst_char_iterate(bst_char *t, char (*fun)(char item)) {
^
pfbst_char.c:389:8: warning: passing argument 1 of ‘bst_char_iterate’ from incompatible pointer type [enabled by default]
bst_char_iterate(p->right,fun);
^
pfbst_char.c:381:5: note: expected ‘struct bst_char *’ but argument is of type ‘struct node *’
int bst_char_iterate(bst_char *t, char (*fun)(char item)) {
^
4. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Jan 2014
Posts
3
Rep Power
0
I have managed to get it to compile with this code:

Code:
```    int bst_iterate(struct node *p, char (*fun)(char item)) {
if (p!=NULL) {
p->item = fun(p->item);
bst_iterate(p->left,fun);
bst_iterate(p->right,fun);
} else {
return 0;
}
}

int bst_char_iterate(bst_char *t, char (*fun)(char item)) {
assert(t!=NULL);
bst_iterate(t->root,(fun));
}```
But I've no idea how to implement it in the program.

I've tried:

Code:
```bst_char_iterate(t, fun);
bst_char_iterate(t, *fun);
bst_char_iterate(t->root, fun);
bst_char_iterate(t, fun(c));```
5. Well first you need to write a function you want to call for each node on the tree.

Say
Code:
```char printit(char item) {
putchar(item);
}```
Then
bst_char_iterate(t, printit);
should do the biz.