Wednesday, September 21, 2011

No. 06 - Post-order Traversal Sequences of Binary Search Trees


Problem: Determine whether an input array is a post-order traversal sequence of a binary tree or not. If it is, return true; otherwise return false. Assume all numbers in an input array are unique.

For example, if the input array is {5, 7, 6, 9, 11, 10, 8}, true should be returned, since it is a post-order traversal sequence of the binary search tree in Figure 1. If the input array is {7, 4, 6, 5}, false should be returned since there are no binary search trees whose post-order traversal sequence is such an array.
Figure 1: A binary search tree with post-order traversal sequence {5, 7, 6, 9, 11, 10, 8}
Analysis: The last number is a post-order traversal sequence is the value of root node. Other numbers in a sequence can be partitioned into two parts: The left numbers, which are less than the value of root node, are value of nodes in left sub-tree; the following numbers, which are greater than the value of root node, are value of nodes in right sub-tree.

Take the input {5, 7, 6, 9, 11, 10, 8} as an example, the last number 8 in this sequence is value of root node. The first 3 numbers (5, 7 and 6), which are less than 8, are value of nodes in left sub-tree. The following 3 numbers (9, 11 and 10), which are greater than 8, are value of nodes in right sub-tree.

We can continue to construct the left sub-tree and right sub-tree according to the two sub-arrays with the same strategy. In the subsequence {5, 7, 6}, the last number 6 is the root value of the left sub-tree. The number 5 is the value of left child since it is less than root value 6, and 7 is the value of right child since it is greater than 6. Meanwhile, the last number 10 in subsequence {9, 11, 10} is the root value of right sub-tree. The number 9 is value of left child, and 11 is value of right child accordingly.

Let us analyze another array {7, 4, 6, 5}. The last number 5 is the value of root node. Since the first number 7 is greater than 5, there are no nodes in the left sub-tree and numbers 7, 4, 6 are all value of nodes in right sub-tree. However, we notice that a number 4, a value in right sub-tree, is less than the root value 5. It violates the definition of binary search trees. Therefore, there are no binary search trees with post-order traversal sequence {7, 4, 6, 5}.

It is not difficult to write code after we get the strategy above. Some sample code is shown below:

bool VerifySquenceOfBST(int sequence[], int length)
{
    if(sequence == NULL || length <= 0)
        return false;

    int root = sequence[length - 1];

    // nodes in left sub-tree are less than root node
    int i = 0;
    for(; i < length - 1; ++ i)
    {
        if(sequence[i] > root)
            break;
    }

    // nodes in right sub-tree are greater than root node
    int j = i;
    for(; j < length - 1; ++ j)
    {
        if(sequence[j] < root)
            return false;
    }

    // Is left sub-tree a binary search tree?
    bool left = true;
    if(i > 0)
        left = VerifySquenceOfBST(sequence, i);

    // Is right sub-tree a binary search tree?
    bool right = true;
    if(i < length - 1)
        right = VerifySquenceOfBST(sequence + i, length - i - 1);

    return (left && right);
}

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages,  please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact the author via zhedahht@gmail.com . Thanks.  

19 comments:

  1. Just do a post-order traversal and keep on incrementing a variable. Other than that check for edge case. Here is my code. Please look at it and if you feel it's missing something let me know.
    bool checkPostOrderUtil( node *root, int arr[], int size, int& i)
    {
    if( root != NULL && i > size-1 )
    return false;
    if( root == NULL )
    return true;
    bool left = checkPostOrderUtil(root->left, arr, size, i);
    bool right = checkPostOrderUtil(root->right, arr, size, i);
    if( root->key == arr[i++])
    return left & right;
    else
    return false;
    }

    bool checkPostOrder(node* root, int arr[], int size)
    {
    int i = 0;
    bool check = checkPostOrderUtil(root, arr, size, i) & (i == size);
    }

    ReplyDelete
    Replies
    1. My bad! I misread the question. Anyway my code returns true if a given array is a post order traversal of a binary tree.

      Delete
    2. First, I want to complement this page administrator for creating this platform for us to express our feelings. Herpes is a serious and recurring disease which can't be cured through drugs or injections by the American doctors but the best way to deal with herpes is by taking natural herbs medicine from DR. ISHIAKU the greatest herbalist doctor in the world and is only few American doctors that know about this herbal medicine from Dr ISHIAKU .. I have read about Dr ISHIAKU the great herbalist doctor from African who can cure disease with his powerful herbal medicine. for the people suffering from the following diseases, Herpes,HIV/Aids, Cancer, Also, Hepatitis, Diabetes, Hpv, Infections ETC should contact him for his herbal medicine because i am a living testimony and i was cured of herpes. Although, i sent him what he requested and he sent me his medicine through DHL courier delivery company which i took for some days and today when i went for test, i was tested herpes negative. you can reach him through his email: ishiakuherbalcure@gmail.com WhatsApp him at +2348180828544  

      Delete
    3. I visited different hospital but they gave me list of expensive drugs to treat the symptoms and never cured me. A closed friend of mine introduce me to a Herbal Doctor who cured her. I was scared to contact him because of what i experienced from fake doctors. she encouraged me and gave me his whatsapp contact,and i contacted him and i asked him series of questions, i also ask him to show me the results of those he have cured with his herbal drugs,and he gave me all the information i needed that gave me hope. He send a Herbal medicine to me that i took and it seriously worked for me. am now Hepatitis negative. God bless you for being a sincere and great man. Am so excited and am free from herpes virus. you can reach him via email;drshaibuabacha@gmail.com or whats-app/call on +2349051727475. He also cure several ailments like ; Mouth odour,  Diabetes, Stroke, Hypertension,  kidney problem, Ex back, Low sperm count, Weak Erection and HIV/Aids. Please do not hide you problems so your problems will not hide you.

      Delete
  2. It can be optimize by doing down to up approach. First check for left and right subtree and then check if root element is smaller than first element of the right sub tree because first element will be smallest element for right sub tree.

    ReplyDelete
    Replies
    1. It will not be correct as if what if there is no left sub-tree?

      Delete
  3. This comment has been removed by the author.

    ReplyDelete
  4. I think, this method will not work in the following case:
    8
    -\
    --10
    ---\
    ----9
    This is not BST, but post-order traversal sequence for it will be {9, 10, 8} and VerifySquenceOfBST define that sequence as BST.

    ReplyDelete
    Replies
    1. In this case, the question will be: "Is [9, 10, 8] a post-order traversal sequence of any BST?"
      The answer is YES, as per the suggested algorithm, which is correct. Look at the following BST:
      ------8
      --------\
      ---------\
      ---------10
      ---------/
      -------9

      Delete
  5. public static boolean isValidPostTraversalArray(int[] arr, int s, int e) {
    if(s >= e) {
    return true;
    }

    int root = arr[e];
    int leftEndIndex = 0;
    for(int i=s; i root) {
    leftEndIndex = i-1;
    break;
    }
    }

    for(int i=leftEndIndex + 1; i<e; i++) {
    if(arr[i] < root) {
    return false;
    }
    }

    return isValidPostTraversalArray(arr, s, leftEndIndex) && isValidPostTraversalArray(arr, leftEndIndex + 1, e - 1);
    }

    ReplyDelete
  6. Let me know how this looks:
    public static boolean isValidBST(int[] post) {
    return isValidBSTHelper(post, 0, post.length-1);
    }

    private static boolean isValidBSTHelper(int[] post, int start, int end) {
    if (start >= end) {
    return true;
    }
    int i = start;
    int root = post[end];
    while (post[i] <= root && i < end) {
    i++;
    }
    for (int k = i; k < end; k++) {
    if (post[k] < root) {
    return false;
    }
    }
    return isValidBSTHelper(post, start, i-1)
    && isValidBSTHelper(post,i,end-1);
    }

    ReplyDelete
  7. Hi There,

    Seems like I won the lottery here….This is a treasure box of blogs and your folks are like leprechauns! Phenomenal read on Post-order Traversal Sequences of Binary Search Trees !


    I'm currently on the free tier and as I'm evaluating the services, I'm liking what I see. Currently my costs are low but this doesn't really help me in my evaluation cost as I'm still not seeing what my true costs would be when the free tier expires. Is there a way to see what my costs "would have been" if I was not on the free tier? I'm aware of the cost estimator, but this is not as helpful to me as knowing what my average true costs would be.




    Please keep providing such valuable information.

    Merci Beaucoup,
    Radhey

    ReplyDelete
  8. Greetings Mate,


    I’ve often thought about this No. 06 - Post-order Traversal Sequences of Binary Search Trees. Nice to have it laid out so clearly. Great eye opener.

    I am using I EC2 instance, but after several trials I can't get more that 2~3Mbits/sec of the internet connection, is there any limits? AWS Training USA


    I did the tests in different hours of the last two days.





    THANK YOU!! This saved my butt today, I’m immensely grateful.


    Gracias
    Ajeeth

    ReplyDelete
  9. I came on the Internet i saw great testimony about DR Voke on how he was able to cure someone from HERPES, and any disease this person said great things about this man, and advice we contact him for any problem that DR Voke can be of help, well i decided to give him a try, he requested for my information which i sent to him, and he told me he was going to prepare for me a healing portion, which he wanted me to take for days, and after which i should go back to the hospital for check up, well after taking all the treatment sent to me by DR Voke i went back to the Hospital for check up, and now i have been confirmed HERPES Negative, friends you can reach Dr voke on any treatment for any Disease, reach him on _________________________________[doctorvoke@yahoo.com]

    ReplyDelete
  10. HAVE YOU BEEN IN SEARCH FOR GENUINE HACKER'S ONLINE?. HAVE YOU LOST YOUR MONEY TO BINARY OPTION SCAM OR ANY ONLINE SCAM WHATSOEVER?. WELL, YOU HAVE FOUND REDEMPTION IN ASORE CORP.
    asorehackcorp@gmail.com

    Asore Corp is a group of multinational Hacker's, an affiliate of Evil Corp. We make sure by all means necessary that our clients get the best of services on a🔐PAYMENT AFTER JOB IS DONE BASIS✅. Rather than send money and trust a criminal to fulfill your deal, you can make sure the job is done before WORKMANSHIP is paid for. You'll get excellent customer service.
    That's a 100% guarantee. Our Cyber security Technicians are on standby 24/7 to receive your job requests.

    ⚠️ BEWARE OF FRAUDSTARS
    if you have been a VICTIM, contact : ✉️cyberprecinct@gmail.com for directives.
    Here, it's always a win for you.

    🔸OUR SERVICES🔸
    ➡️Binary Option funds recovery
    ➡️Social media hack
    ➡️Recovery of loan scam
    ➡️Credit repair (Equifax,Experian,Transunion)
    ➡️E mail hack
    ➡️College score upgrade
    ➡️Android & iPhone Hack
    ➡️Website design
    ➡️Website hack
    ➡️And lots more.

    DISCLAIMER: Asore Cyber Corp accepts no responsibility for any information,previously given to anybody by clients on as regarding the job. Asore Cyber Corp will not distribute contact information collected on any hacking job other than in the Asore corps Hacker's listings themselves, and will not sell contact information to third parties.

    CONTACT INFO:
    📧 asorehackcorp@gmail.com
    cyberprecinct@gmail.com

    Copyright ©️
    Asore Cyber Corp 2021.
    All rights reserved.

    ReplyDelete
  11. I visited different hospital but they gave me list of expensive drugs to treat the symptoms and never cured me. A closed friend of mine introduce me to a Herbal Doctor who cured her. I was scared to contact him because of what i experienced from fake doctors. she encouraged me and gave me his whatsapp contact,and i contacted him and i asked him series of questions, i also ask him to show me the results of those he have cured with his herbal drugs,and he gave me all the information i needed that gave me hope. He send a Herbal medicine to me that i took and it seriously worked for me. am now Hepatitis negative. God bless you for being a sincere and great man. Am so excited and am free from herpes virus. you can reach him via email;drshaibuabacha@gmail.com or whats-app/call on +2349051727475. He also cure several ailments like ; Mouth odour,  Diabetes, Stroke, Hypertension,  kidney problem, Ex back, Low sperm count, Weak Erection and HIV/Aids. Please do not hide you problems so your problems will not hide you.

    ReplyDelete
  12. Quality beauty products at Alidereva
    Products reviews at Sociopins

    ReplyDelete