Traversal (inorder,preorder,postorder) of Binary Tree using recursion and also iteratively in c.

Hi friends,
      I will focus on how to traverse binary tree using iterative method which is tricky as compared to traversal using recursion. Consider following binary tree for example:

Inorder traversal means (left,visit,right) for every node starting from root .Inorder traversal for above tree gives:               1 3 4 6 7 8 10 13 14

Preorder traversal means (visit,left,right) for every node starting from root .Preorder traversal for above tree gives:               8 3 1 6 4 7 10 14 13

Postorder traversal means (left,right,visit) for every node starting from root .Postorder traversal for above tree gives:               1 4 7 6 3 13 14 10 8

Assume Node defination as:

typedef struct BinaryTreeNode
{
    int key;
    struct BinaryTreeNode *left,*right,*parent;
}TreeNode;

/*Recursive Inorder traversal: This traversal print keys in non-decreasing sorted order */

void traverse_inorder_rec(TreeNode *root)
{
    if(root!=NULL)
    {
        traverse_inorder_rec(root->left);
        printf("%d ",root->key);
        traverse_inorder_rec(root->right);
    }
}

/*Recursive Preorder traversal*/

void traverse_preorder_rec(TreeNode *root)
{
    if(root!=NULL)
    {
        printf("%d ",root->key);
        traverse_preorder_rec(root->left);
        traverse_preorder_rec(root->right);
    }
}

/*Recursive Postorder traversal: This traversal is helpful for deleting tree*/

void traverse_postorder_rec(TreeNode *root)
{
    if(root!=NULL)
    {
        traverse_postorder_rec(root->left);
        traverse_postorder_rec(root->right);
        printf("%d ",root->key);
    }
}

/*In all 3 iterative traversals we use stack as auxiliary data structure*/

/*Iterative Preorder: This is the most easiest among all 3 iterative traversals*/

void traverse_preorder_iterative(TreeNode *root)
{
    /*
    *Node's currently on stack are nodes whose keys are to be printed
    and left and right both child to be processed later.

    *All TreeNode * in stack are non NULL
    */
    stack<TreeNode *> s;
    if(root!=NULL)
    {
        s.push(root);
        while(!s.empty())
        {
            TreeNode *ptr=s.top();
            s.pop();
            printf("%d ",ptr->key);
            if(ptr->right!=NULL)
                s.push(ptr->right);
            if(ptr->left!=NULL)
                s.push(ptr->left);
        }
    }
}

/*Iterative Inorder traversal*/

void traverse_inorder_iterative(TreeNode *root)
{
        stack<TreeNode *> s;
        TreeNode *current=root;
        bool done =false;
        while(!done)
        {
            if(current)
            {
                s.push(current);
                current=current->left;
            }
            else
            {
                if(s.empty())
                {
                    done=true;
                }
                else
                {
                    current=s.top();
                    s.pop();
                    cout<<current->key<<" ";
                    current=current->right;
                }
            }
        }
}

/*Iterative post order traversal: This is the most trickiest among all this 3 iterative versions.Here we use prevNode pointer for keeping track in which direction we are moving.For eg. Either (upward from left or right ) or (downward from left or right )*/

void traverse_postorder_iterative(TreeNode *root)
{
    if(root!=NULL)
    {
        stack<TreeNode *> s;
        TreeNode *prevNode,*currentNode;
        prevNode=NULL;
        s.push(root);

        while(!s.empty())
        {
            currentNode=s.top();
            if(prevNode==NULL || prevNode->left==currentNode ||                            
                prevNode->right==currentNode)
            {
                if(currentNode->left!=NULL)
                    s.push(currentNode->left);
                else if(currentNode->right!=NULL)
                    s.push(currentNode->right);
                else
                {
                    printf("%d ",currentNode->key);
                    s.pop();
                }
            }
            else if(prevNode==currentNode->left)
            {
                if(currentNode->right!=NULL)
                    s.push(currentNode->right);
                else
                {
                    printf("%d ",currentNode->key);
                    s.pop();
                }
            }
            else if(prevNode==currentNode->right)
            {
                printf("%d ",currentNode->key);
                s.pop();
            }
            prevNode=currentNode;
        }
    }
}

Please comment if any doubt and like if helpful.

For detail explanation of postorder iterative version ,refer to link:http://leetcode.com/2010/10/binary-tree-post-order-traversal.html

Creating pascal triangle using 1-Dimensional array for finding coefficients of (1+x)^n efficiently.

Hi friends,
     As you all know pascal triangle looks like
                                                                     1                                      n=0
                                                                 1      1                                  n=1
                                                             1      2      1                              n=2
                                                          1     3       3      1                         n=3
                                                       1     4     6      4      1                      n=4
                                                    1     5    10   10     5     1                   n=5
                                                 ............................................                so on
Observe some facts:
1)Number of element in ith row = (i+1)

2) ith element in nth row = sum of (i-1)th & (i)th element in (n-1)th row  for 1<i<(n+1)

3)Also ,
For n=0:     (1+x)^0=1
For n=1:     (1+x)^1=1 + 1*(x)
For n=2:     (1+x)^2=1 + 2*(x) + 1*(x*x)
For n=3:     (1+x)^3=1 + 3*(x) + 3*(x*x) + 1*(x*x*x)

Observe the coefficients underlined, they belongs to each row of above triangle. For eg. when n=2,
coefficients are (1,2,1) which is row number 2 of pascal triangle. Similar situation occurs for n=3,here
coefficients are (1,3,3,1) which is row number 3 of pascal triangle.

4)Coefficients of (1+x)^n form sequence :      (nC0,nC1,nC2,.....nCn)    
where nCr=(n!)/(r! * (n-r)!)

So,by finding nth row of pascal triangle we are finding coefficients of (1+x)^n and hence indirectly above sequence of combinations.

Now we will see how to generate above pascal triangle recursively for specified value of 'n' using 1-D array in c++.

Size of 1-D array for above triangle for some n = 1+2+3+....+(n+1) =
 ((n+1)*(n+2))/2

Starting index in this 1-D array for nth row of  pascal triangle= 1+2+...n =
(n*(n+1))/2

//Actual c++ routine starts here:

void Form_Pascal_Triangle(unsigned long int a[],unsigned long int n)
{
    if(n==0)
    {
        a[0]=1;
    }
    else
    {
        Form_Pascal_Triangle(a,n-1);

        unsigned long int PREVTO_NTH_ROW_START_INDEX=(n*(n-1))/2;

        unsigned long int CURRENT_NTH_ROW_START_INDEX=(n*(n+1))/2;

        //initialise first and last element of nth row of pascal triangle
        a[CURRENT_NTH_ROW_START_INDEX]=1;
        a[CURRENT_NTH_ROW_START_INDEX+n]=1;

        for(unsigned long int i=1;i<n;i++)
        {
             a[CURRENT_NTH_ROW_START_INDEX+i] =
                                       a[PREVTO_NTH_ROW_START_INDEX+i-1] +
                                       a[PREVTO_NTH_ROW_START_INDEX+i];
        }
    }
}


int main()
{
    unsigned long int n;
    cout<<"Enter n:";
    cin>>n;
    unsigned long int size=((n*(n+1))/2)+(n+1);
    unsigned long int a[size];
 
    Form_Pascal_Triangle(a,n);

    return 0;
}

Please comment if any doubt and like if helpful.Thanks