Problem
An array which is a Post order traversal of a Binary Tree. Write a function to check if the Binary Tree formed from the array is a Binary Search Tree.Eg:
2
1 3
The array given as input would be 1 3 2.
Write a function to say if the tree formed is a Binary Search Tree.
Example 2: 4 is root. 0 is left child of 1 , 1 is left child of 2 and 2 is left child of 4. 5 is right child of 4 and 6 is right child of 5.
4
2 5
1 6
0
0 1 2 6 5 4 is the input array. Also, post order traversal has been explained here as well.
Solution
Consider the solution given here.We know in BST root is bigger than all nodes in left subtree and is no larger than all nodes in right subtree. Thus, if the array is a post traversal of a BST, then arr[n-1] can divide the array into two parts arr[0, i) and arr[i, n-1), where
(1)each item in arr[0, i) is less than arr[n-1]
(2)each item in arr[i, n-1) is not less than arr[n-1]
(3)both arr[0, i) and arr[i, n-1) are post traversals of BSTs.
bool isPostTraversalOfBST(int arr[], int n)
{
if(n < 2) return true;
int i = 0;
//try to find out the beginning of right subtree's traversal
for(; arr[i] < arr[n-1]; ++i) ;
//check if all arr[i,n-1) >= arr[n-1]
for(int j = i + 1; j + 1 < n; ++j){
if(arr[j] < arr[n-1]) return false;
}
//check if both two parts are post traversals of BSTs
return isPostTraversalOfBST(arr, i) &&
isPostTraversalOfBST(arr + i, n - i - 1);
}