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.  

10 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. 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