1. ## Preorder Traversal

Alright I have seen a bunch of algorithms now, that I don't fully understand. I am trying to count leafs and non-leafs of a binary tree

I have this header struct for a binary tree where pRoot is the root
Code:
```typedef struct BST
{
char city[50];
char zipcode[8];
char state[2];
double latitude;
double longitude;
long population;
struct BST *left;
struct BST *right;
struct BST *parent;
}Tree_node;

typedef struct
{
struct BST *pRoot;
int itree_node_count;
int idepth;
int leaves[500];
int non_leaves[500];
I am declaring my fiunction like this
Code:
`	int Traverse(Tree_Header *psTree, int);`
calling it like this
CODE]Traverse(psTree, 0);[/CODE]

and then the function looks like this

Code:
```Traverse(Tree_Header *psTree, int ilevel)
{

//visit
if(psTree->pRoot->left == NULL && psTree->pRoot->right == NULL)
{
//increment leaves
psTree->leaves[ilevel]++;

}
else
{
//increment non_leaves
psTree->non_leaves[ilevel]++;
}
Traverse(psTree->pRoot->left, ilevel+1);
Traverse(psTree->pRoot->right, ilevel+1);

return 0;
}```
I wish I understood recursion better but I don't . If there is anyone that can help me with this, I would be very thankful because I am tired of beating my head on this keyboard

2. BTW

here are the warnings I am getting, I would assume they have something to do with it

\\COMP.UARK.EDU\HOMES\wog41.c(677) : warning C4133: 'function' : incompatible types - from 'struct BST *' to 'struct Tree_Header *'
\\COMP.UARK.EDU\HOMES\wog41.c(678) : warning C4133: 'function' : incompatible types - from 'struct BST *' to 'struct Tree_Header *'

3. > Traverse(Tree_Header *psTree, int ilevel)
Traverse(BST *psTree, int ilevel)
seems much better to me - Tree_Header is just something to hold the tree and a bit of additional information.

Start by calling it with
Traverse(psTree->pRoot, 0);

4. does it matter if I don't change it to BST?
It gives me a whole bunch of crazy errors when I do

changed this though
Traverse(psTree->pRoot, 0);
but still doesn't clear anything up

5. Once you're into the BST part, you do this...

Traverse(psTree->left, ilevel+1);
Traverse(psTree->right, ilevel+1);

6. changing my declarations to BST
like this
Code:
`int Traverse(BST *psTree, int);`
Code:
```Traverse(BST *psTree, int ilevel)
{

//visit
if(psTree->left == NULL && psTree->right == NULL)
{
//increment leaves
psTree->leaves[ilevel]++;

}
else
{
//increment non_leaves
psTree->non_leaves[ilevel]++;
}

Traverse(psTree->left, ilevel+1);
Traverse(psTree->right, ilevel+1);
return 0;
}```
this gives me these errors
\COMP.UARK.EDU\HOMES\wog41.c(103) : error C2059: syntax error : ','
\\COMP.UARK.EDU\HOMES\wog41.c(103) : error C2143: syntax error : missing ')' before '*'
\\COMP.UARK.EDU\HOMES\wog41.c(103) : error C2143: syntax error : missing ';' before '*'
\\COMP.UARK.EDU\HOMES\wog41.c(103) : error C2059: syntax error : 'type'
\\COMP.UARK.EDU\HOMES\wog41.c(103) : error C2059: syntax error : ')'
\\COMP.UARK.EDU\HOMES\wog41.c(662) : error C2143: syntax error : missing ')' before '*'
\\COMP.UARK.EDU\HOMES\wog41.c(662) : error C2143: syntax error : missing '{' before '*'
\\COMP.UARK.EDU\HOMES\wog41.c(662) : error C2059: syntax error : 'type'
\\COMP.UARK.EDU\HOMES\wog41.c(662) : error C2059: syntax error : ')'
Error executing cl.exe.

wog41.obj - 9 error(s), 0 warning(s)

7. line 103 is the top one
and line 662 is the bottom one

8. Looks like it doesn't know what "BST" is.
Try "struct BST" or use the typedef "Tree_node".

gg

9. i used struct BST for both

Code:
`int Traverse(struct BST *psTree, int);`
Code:
```Traverse(struct BST *psTree, int ilevel)
{
int leaves[500], non_leaves[500];

//visit
if(psTree->left == NULL && psTree->right == NULL)
{
//increment leaves
leaves[ilevel]++;

}
else
{
//increment non_leaves
non_leaves[ilevel]++;
}

Traverse(psTree->left, ilevel+1);
Traverse(psTree->right, ilevel+1);
return 0;
}```
no errors, but it crashes

10. anyone have any ideas?

11. can someone seriously help?
I will even post the algorithm on here that everybody gives me.
I have been working on this one function for 8-9 hours now. I just want to understand it.

12. Well the introduction of local variables for your arrays is probably not what you want, because all your results will be lost.

So I think it should be like this - note the extra param
Code:
```typedef struct BST
{
char city[50];
char zipcode[8];
char state[2];
double latitude;
double longitude;
long population;
struct BST *left;
struct BST *right;
struct BST *parent;
}Tree_node;

typedef struct
{
struct BST *pRoot;
int itree_node_count;
int idepth;
int leaves[500];
int non_leaves[500];

Traverse( Tree_Header *info, struct BST *psTree, int ilevel)
{
//visit
if(psTree->left == NULL && psTree->right == NULL)
{
//increment leaves
info->leaves[ilevel]++;

}
else
{
//increment non_leaves
info->non_leaves[ilevel]++;
}

Traverse(info, psTree->left, ilevel+1);
Traverse(info, psTree->right, ilevel+1);