Various traversal of Binary Trees

Binary trees can be traversed by three simple methods. That are:
1) In-order
2) Pre-order
3) Post- order

More on tree traversal

To traverse a non-empty binary tree in inorder (symmetric), perform the following operations recursively at each node:

1. Traverse the left subtree.
2. Visit the root.
3. Traverse the right subtree.

To traverse a non-empty binary tree in preorder, perform the following operations recursively at each node, starting with the root node:

1. Visit the root.
2. Traverse the left subtree.
3. Traverse the right subtree.

To traverse a non-empty binary tree in postorder, perform the following operations recursively at each node:

1. Traverse the left subtree.
2. Traverse the right subtree.
3. Visit the root.

C program below illustrates three of the traversal carefully :-

struct node {

    struct node *left;

    int data;

    struct node *right;

};

void insert(struct node **p, int n) {

    if(*p == NULL) {

        *p = (struct node*) malloc(sizeof(struct node));

        (*p)->left = NULL;

        (*p)->data = n;

        (*p)->right = NULL;

    }

    else {

        if(n < (*p)->data)

            insert(&((*p)->left), n);

        else

            insert(&((*p)->right), n);

    }

}

void inorder(struct node* p) {

    if(p != NULL) {

        inorder(p->left);

        printf("%d ",p->data);

        inorder(p->right);

    }

}

void preorder(struct node* p) {

    if(p != NULL) {

        printf("%d ",p->data);

        preorder(p->left);

        preorder(p->right);

    }

}

void postorder(struct node* p) {

    if(p != NULL) {

        postorder(p->left);

        postorder(p->right);

        printf("%d ",p->data);

    }

}

int main() {

    struct node *bt = NULL;

    int t,n,i=0;

    scanf("%d",&t);

    while(t--) {

        scanf("%d",&n);

        insert(&bt, n);

        //Address to the pointer is passed to

        //retain the value of root node.

    }

    printf("In-order is:\n");

    inorder(bt);

    printf("\nPre-order is:\n");

    preorder(bt);

    printf("\nPost-order is:\n");

    postorder(bt);

    return 0;

}

Comparison of some algorithms of Fibonacci numbers

There are two algorithms by which you can find fibonacci numbers :
1) Recursively, and
2) Dynamic programming

1) Recursively :


int fibonacci(int n) {
    if(n == 1)
        return 0;
    if(n == 2)
        return 1;
    return (fibonacci(n-1) + fibonacci(n-2));
}


Large time is taken for large input in recursive algorithm.
for example : n = 45, it takes 10 sec to solve.

Recursive algorithm solves one fibonacci(k) many times so, for large values of n.

So we use dynamic programming. Optimal solution is found in dynamic programming part.



2) Dynamic programming :


int main() {
    int n,i,a,b,t;
    cin>>n;
    if(n  == 1)
        a = 0;
    else
        a = 1;
    b = 0;
    for(i=2;i<n;i++) {
        t = a;
        a += b;
        b = t;
        cout<<a<<" ";
    }
    return 0;
}