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

Connecting to gmail and downloading all mails in .mbox file format on local hard drive using python is so easy.Try it

Note that this script marks all mails in your mailboxes as read so be careful. Also I am not responsible for any data loses or corruption.Save this with some filename with .py extension and run it from command line as filename.py. Also this is written for 3.x python version. 

 

import imaplib,re,mailbox
from email.parser import BytesParser
class mbox:
def __init__(self,filename):

filename=filename.split('/')[-1]+".mbox"

#print(filename)
self.file_handle=mailbox.mbox((filename))

def dump_mails(self,msg_list):
try:
self.file_handle.lock()

for each_msg in msg_list:
mbox_msg=mailbox.mboxMessage(each_msg)
self.file_handle.add(mbox_msg)

self.file_handle.flush()
finally:
self.file_handle.unlock()

def close(self):
self.file_handle.close()



class gmail:
def __init__(self):
self.IMAP_SERVER='imap.gmail.com'
self.IMAP_PORT=993
self.M = None
self.response=None
self.mailboxes=[]

def connect(self,username,password):
self.M=imaplib.IMAP4_SSL(self.IMAP_SERVER,self.IMAP_PORT)
status,self.response=self.M.login(username,password)
return status

def get_mailboxes(self):
rc,self.response=self.M.list()
#pattern=r'"([[a-zA-Z0-9]+]/)*[a-zA-Z0-9 ]+"'
pattern=r'".*?"'
pattern=re.compile(pattern)

for item in self.response:
item=item.decode("ascii")
folder_subpath_list=pattern.findall(item)
self.mailboxes.append(folder_subpath_list[-1][1:-1])
#print("self.mailbox",self.mailboxes)
return self.mailboxes

def get_mailcount(self,mailbox='inbox'):
rc,self.response=self.M.select(mailbox)
self.mailcount=int(self.response[0])
return self.mailcount

def get_unread_mailcount(self,mailbox='inbox'):
rc,message=self.M.status(mailbox,"(UNSEEN)")
for item in message:
print("message item= ",item)
unreadCount = re.search("UNSEEN (\d+)", str(message[0])).group(1)
return unreadCount

def rename_mailbox(self, oldmailbox, newmailbox):
rc, self.response = self.M.rename(oldmailbox, newmailbox)
return rc

def create_mailbox(self, mailbox):
rc,self.response= self.M.create(mailbox)
return rc

def delete_mailbox(self, mailbox):
rc, self.response = self.M.delete(mailbox)
return rc

#retrieves all mails and probably marks them as read so be carefull
def get_all_mails(self,mailfolder):

#select specified mailfolder at server
rc,self.response=self.M.select(mailbox=mailfolder)

#get mail numbers list
status,data=self.M.search(None,'ALL')

mail_obj_list=[]
for mail_no in data[0].split():
status,mail=self.M.fetch(mail_no,'(RFC822)')
mail_obj=BytesParser().parsebytes((mail[0][1]))
mail_obj_list.append(mail_obj)
return mail_obj_list

def disconnect(self):
self.M.logout()

#main script starts

gmail_link=gmail()
username=input('Enter username:').strip()
password=getpass.getpass()
print ("connecting...")
print (gmail_link.connect(username,password),gmail_link.response)

print ("Retrieving mailboxes...")
mailboxes=gmail_link.get_mailboxes()
print ("Done...")

for mailbox in mailboxes:
try:
if mailbox.find(' ')!=-1:
continue
print ("Processing mailbox:",mailbox)

#get all mails_list present in mailbox
mails=gmail_link.get_all_mails(mailfolder=mailbox)

#create new mailbox(type =mbox) for each folder(mailbox)
mailbox_handle=mbox(filename=mailbox)

#add mails to mailbox created
mailbox_handle.dump_mails(mails)
print ("Processing mailbox:",mailbox,"done")
except:
print("Could not retrieve from mailbox:",mailbox)
finally:
mailbox_handle.close()
print("Disconnecting...")
gmail_link.disconnect()