Python is awesome

I present for your consideration the following problem given a preorder and inorder transversal of a tree construct the postorder traversal

Consider the following tree

     D
    / \
   /   \
  B     F
 / \   / \
A   C E   G

• prefix: DBACFEG
• infix: ABCDEFG
• postfix: ACBEGFD

The goal is to generate the postfix representation from the first two. When you look at the problem for a little bit you should be able to find some clues to start. First look at the sections of the prefix and infix

 M  L   R
 D BAC FEG

  L  M  R
 ABC D EFG

So the first place to start is to find the root of the tree and the left and right branches. The root is the first element of the prefix representation(D). The root is the identical element in the infix notation(D). The left branch is the elements to the left of the root in the infix notation(ABC). The left branch in the prefix notation is the elements starting just to the right of the root and are the same size as the infix(BAC). The right branch of the tree is the elements to the right of the root in infix notation(EFG). The right branch is the same number of elements beginning after the left branch in the prefix notation(FEG).

Once the root and branches are identified only two parts remain. The branches and roots must be rearranged into postfix notation. The left and right branches must be parsed into postfix notation. The most reasonable way to parse each of the branches recursively.

The code for the algorithm is listed in python3 below:

def postfix(prefix,infix):
	# Base case
	if(prefix==""):
		return ""
	
	# Find the root
	root = prefix[0];
	index = infix.find(root)
	
	# recursively parse the left branch
	left=postfix(prefix[1:1+index],infix[:index])
	# recursively parse the right branch
	right=postfix(prefix[1+index:],infix[index+1:])
	#assign the root to middle
	middle=root	
	
	# put it all together
	return left+right+middle

For comparison the code in C is listed here:

#include <string.h>
#include <stdio.h>

int MAX_LENGTH = 26;

void substring(char const * original, char * result,int start, int stop);
void postfix(char const * prefix, char const * infix, char * postfix);


//replaces array splice in Python
void substring(char const * original, char * result,int start, int stop)
{
    strncpy(result, &original[start], stop-start);
    result[stop-start]='\0';
}


void postfix(char const * pre, char const * in, char * post)
{
    //handels base cases for C
    if(strlen(pre) ==0)
    {
        return;
    }
    else if (strlen(pre)==1)
    {
        strcpy(post,pre);
        return;
    }
    
	char root = pre[0];
    
    //index = inorder.find(root)
	int index;
	for(int i = 0; i < strlen(in);++i)
	{
        if(in[i]==root)
        {
            index = i;
        }
	}
    
    char leftPrefix[MAX_LENGTH];
    char rightPrefix[MAX_LENGTH];
    char leftInfix[MAX_LENGTH];
    char rightInfix[MAX_LENGTH];
    char leftPostfix[MAX_LENGTH];
    char rightPostfix[MAX_LENGTH];

    //preorder[1:1+index]
    substring(pre,leftPrefix,1,1+index);
    //inorder[:index]
    substring(in,leftInfix,0,index);
    
    //preorder[1+index:]
    substring(pre,rightPrefix,1+index,(int)strlen(pre));
    //inorder[index+1:]
    substring(in,rightInfix,index+1,(int)strlen(in));
    
    
    char left[MAX_LENGTH];
    char right[MAX_LENGTH];
	
	
    //left=postfix(prefix[1:1+index],infix[:index])
    postfix(leftPrefix,leftInfix,leftPostfix);
    sprintf(left, "%s",leftPostfix);
    //right=postfix(prefix[1+index:],infix[index+1:])
    postfix(rightPrefix,rightInfix,rightPostfix);
    sprintf(right, "%s",rightPostfix);
    //middle=root	
    char middle[3];
	sprintf(middle,"%c", root);
    //return left+right+middle
	sprintf(post,"%s%s%s", left, right, middle);
}

The difference is shocking. The Python code is elegant compact and readable. The C code is long, clunky, and was a pain to debug. The Python array splice notation is powerful and compact. The String object in Python make it easy to copy strings and substrings. The ability to return strings is another phenomenal advantage over the C approach. I found the problem fascinating and the relative results in each language insightful. I hope someone else finds this interesting.