verify if a sequences is the post order traversal of a tree

public boolean postOrderCheck( int sequences[], int length )
    {
        if( sequences == null || sequences.length == 0 )
        {
            return false;
        }

        // boundary-1 would be the index of left child
        // length - 2 would be the root of right child
        int boundary = foundBoundary( sequences, length );
        // from the boundary to the length -2 node, all must be larger than
        // the last one, because they are all belong to right child of root
        boolean result = confirmRightChild( sequences, length, boundary );
        if( !result )
        {
            return false;
        }

        int newSeq[length-boundary];
        for( int i = boundary; i < length-1; i++ )
        {
            newSeq[i-boundary] = sequences[i];
        }

        return ( postOrderCheck( sequences, boundary - 1 )  && ( newSeq, length - boundary ) );

    }

    public int foundBoundary( int sequences[], int length )
    {
        int index = 0;
        if( sequences == null || sequences.length == 0 )
        {
            return -1;
        }
        for( int i = 0; i < sequences.length; i++ )
        {
            if( sequences[i] < sequences[length - 1] )
            {
                continue;
            }
            index = i;
        }

    }

    public boolean confirmRightChild(  int sequences[], int length, int boundary )
    {
        boolean isValid = false;
        if( sequences == null || sequences.length == 0 )
        {
            return isValid;
        }
        int i = 0;
        for( i = boundary; i < length-1; i++ )
        {
            if( sequences[i] < sequences[length -1] )
            {
                break;
            }
        }

        if( i == length-2 )
        {
            isValid = true;
        }
        return isValid;

    }

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s