Traversal

#include <queue>
#include <iostream>
using namespace std;

struct node{
    node(int x, node* l, node* r);
    int c;
    node* left;
    node* right;

    //bool operator<(conc node &rhs) conc{
    //  return ( c < rhs.c );
    //}
};

node::node(int x, node* l=0, node* r=0){
    c = x;
    left = l;
    right = r;
}

void prewalk(node* nd){ //print, left, right
    cout<< nd->c <<" ";
    if (nd->left != 0 )
        prewalk(nd->left);
    if (nd->right != 0 )
        prewalk(nd->right);
    //better sol
    /*
    if (nd == 0) return;
    cout<< nd->c << " ";
    prewalk(nd->left);
    prewalk(nd->right);
    */

}
void postwalk(node* nd){ //left, right, print
    if (nd->left != 0 )
        postwalk(nd->left);
    if (nd->right != 0 )
        postwalk(nd->right);
    cout<< nd->c <<" ";
    //better sol
    /*
    if (nd == 0) return;
    postwalk(nd->left);
    postwalk(nd->right);
    cout<< nd->c << " ";
    */

}
void inwalk(node* nd){ //left, print, right
    if (nd->left != 0 )
        inwalk(nd->left);
    cout<< nd->c <<" ";
    if (nd->right != 0 )
        inwalk(nd->right);
    //better sol
    /*
    if (nd == 0) return;
    inwalk(nd->left);
    cout<< nd->c << " ";
    inwalk(nd->right);
    */
}

void bfirstwalk(node* root){
    queue <node*> q;
    node* n;
    q.push(root);
    while ( !q.empty() )
    {
        n = q.front();
        cout << n->c <<" ";
        if ( n->left != 0 )
            q.push(n->left);
        if ( n->right != 0 )
            q.push(n->right);

        q.pop();
    }
    cout<<endl;
}

//alternate method which pushes null nodes
/*
void bfirstwalk(node* root){
    queue <node*> q;
    node* n;
    q.push(root);
    while ( !q.empty() )
    {
        if (q.front() != 0)
        {
            n = q.front();
            cout << n->c <<",";
            q.push(n->left);
            q.push(n->right);
        }
        q.pop();
    }
    cout<<endl;
}
*/

/*
node* NewNode(int c){
    node* np = new node;
    np->c = c;
    np->left = 0;
    np->right = 0;
    return np;
}
*/
/* must pass nd by ref since we may need to insert at the
root node if tree is empty and hence change the root addr */
void insert(node* &nd, int c){
    if (nd == 0)
    {
        //nd = NewNode(c);
        nd = new node(c);
        return;
    }
    if (c < nd->c)
    {
        insert(nd->left, c);
    }
    else
    {
        insert(nd->right, c);
    }
}


void btfree(node* nd){ //must be post order for deleting (fails if root=0)
    if (nd->left != 0)
        btfree(nd->left);
    if (nd->right != 0)
        btfree(nd->right);
    delete nd;
    nd = 0;
    //better sol
    /*
    if (nd == 0) return;
    btfree(nd->left);
    btfree(nd->right);
    delete nd;
    nd = 0;
    */
}

//alternate better solution (check after instead of before)
/*
void btfree(node* nd){ //must be post order for deleting
    if (nd !=0)  //same as if (nd)
    {
        btfree(nd->left);
        btfree(nd->right);
        delete nd;
        nd = 0;
    }
}
*/

int main(){

    const int iarray[7] = {4,2,6,1,3,5,7};
    node* root=0;

    int x;
    for (x=0; x < 7 ; x++)
    {
        insert(root, iarray[x]);
        //walk(root);
        //cout<<endl;
    }
    cout<<"prewalk ";
    prewalk(root);
    cout<<endl;

    cout<<"postwalk ";
    postwalk(root);
    cout<<endl;

    cout<<"inwalk ";
    inwalk(root);
    cout<<endl;

    cout<<"bfirstwalk ";
    bfirstwalk(root);
    cout<<endl;

    btfree(root);
    return (0);
}