Determine whether a BST is skewed from its preorder traversal
Given an array representing the preorder traversal of a BST, determine whether it represents a skewed BST.
For example,
Output: BST is skewed
Explanation: The Preorder traversal [15, 30, 25, 18, 20] represents the following skewed BST:
In a skewed BST, each node’s descendants are either smaller or larger than the node itself. This property holds for every node in the skewed BST. Therefore, in a preorder traversal of the skewed BST, each node’s descendants appear on the right, and all descendants must be either smaller or greater.
We can use the above property of skewed BST to solve this problem. The idea is to traverse the preorder sequence, and for each element, check if all values on the right are either smaller or larger. This can be easily done using two nested loops and in O(n2) time, where n is the size of the given sequence.
We can solve the problem in O(n) time by doing a single traversal of the array. The idea is to traverse the given preorder sequence from the end, keep track of the minimum and the maximum value found so far. Then for each encountered node, its value must be less than the minimum value so far or more than the maximum value found. The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; // Function to determine whether the given preorder traversal of a // binary tree represents a skewed BST bool isSkewedBST(vector<int> &pre) { // get the size of the preorder sequence int n = pre.size(); // base case: if BST has two or fewer nodes if (n <= 2) { return 1; } // initialize `min_so_far` and `max_so_far` with the last two elements // in the preorder sequence int min_so_far = min(pre[n-1], pre[n-2]); int max_so_far = max(pre[n-1], pre[n-2]); // start from the third element from the end of the preorder sequence for (int i = n - 3; i >= 0; i--) { // check if the current element is in a valid range and update // `min_so_far` & `max_so_far` for the next iteration of the loop if (pre[i] < min_so_far) { min_so_far = pre[i]; } else if (pre[i] > max_so_far) { max_so_far = pre[i]; } else { return false; } } return true; } int main() { vector<int> pre = { 15, 30, 25, 18, 20 }; bool isSkewed = isSkewedBST(pre); if (isSkewed) { cout << "BST is skewed"; } else { cout << "BST is not skewed"; } return 0; } |
Output:
BST is skewed
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
class Main { // Function to determine whether the given preorder traversal of a // binary tree represents a skewed BST public static boolean isSkewedBST(int[] pre) { // get the size of the preorder sequence int n = pre.length; // base case: if BST has two or fewer nodes if (n <= 2) { return true; } // initialize `min_so_far` and `max_so_far` with the last two elements // in the preorder sequence int min_so_far = Integer.min(pre[n-1], pre[n-2]); int max_so_far = Integer.max(pre[n-1], pre[n-2]); // start from the third element from the end of the preorder sequence for (int i = n - 3; i >= 0; i--) { // check if the current element is in a valid range and update // `min_so_far` & `max_so_far` for the next iteration of the loop if (pre[i] < min_so_far) { min_so_far = pre[i]; } else if (pre[i] > max_so_far) { max_so_far = pre[i]; } else { return false; } } return true; } public static void main(String[] args) { int[] pre = { 15, 30, 25, 18, 20 }; boolean isSkewed = isSkewedBST(pre); if (isSkewed) { System.out.println("BST is skewed"); } else { System.out.println("BST is not skewed"); } } } |
Output:
BST is skewed
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
# Function to determine whether the given preorder traversal of a # binary tree represents a skewed BST def isSkewedBST(pre): # get the size of the preorder sequence n = len(pre) # base case: if BST has two or fewer nodes if n <= 2: return 1 # initialize `min_so_far` and `max_so_far` with the last two elements # in the preorder sequence min_so_far = min(pre[n - 1], pre[n - 2]) max_so_far = max(pre[n - 1], pre[n - 2]) # start from the third element from the end of the preorder sequence for i in reversed(range(0, n - 2)): # check if the current element is in a valid range and update # `min_so_far` & `max_so_far` for the next iteration of the loop if pre[i] < min_so_far: min_so_far = pre[i] elif pre[i] > max_so_far: max_so_far = pre[i] else: return 0 return 1 if __name__ == '__main__': pre = [15, 30, 25, 18, 20] if isSkewedBST(pre): print('BST is skewed') else: print('BST is not skewed') |
Output:
BST is skewed
Alternatively, we can start from the beginning of the array and set the range for the elements to follow. Basically, we restrict each preorder descendant to the valid range for the given preorder traversal to represent a skewed BST. The algorithm can be implemented as follows in C, Java, and Python:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include <stdio.h> #include <limits.h> // Function to determine whether the given preorder traversal of a binary tree // represents a skewed BST int isSkewedBST(int pre[], int n) { // initialize the range (min, max) with (-INF, INF) int min = INT_MIN, max = INT_MAX; // start from the second element in the preorder sequence for (int i = 1; i < n; i++) { // if the current element is in a valid range if (pre[i] >= min && pre[i] <= max) { // update a valid range for the next element in the preorder sequence if (pre[i] > pre[i-1]) { min = pre[i-1] + 1; } else { max = pre[i-1] - 1; } } // return false if the current element in the preorder sequence // is not in a valid range else { return 0; } } return 1; } int main(void) { int pre[] = { 15, 30, 25, 18, 20 }; int n = sizeof(pre) / sizeof(pre[0]); int isSkewed = isSkewedBST(pre, n); if (isSkewed) { printf("BST is skewed"); } else { printf("BST is not skewed"); } return 0; } |
Output:
BST is skewed
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
class Main { // Function to determine whether the given preorder traversal of a binary tree // represents a skewed BST public static boolean isSkewedBST(int[] pre) { // initialize the range (min, max) with (-INF, INF) int min = Integer.MIN_VALUE, max = Integer.MAX_VALUE; // start from the second element in the preorder sequence for (int i = 1; i < pre.length; i++) { // if the current element is in a valid range if (pre[i] >= min && pre[i] <= max) { // update a valid range for the next element in the preorder sequence if (pre[i] > pre[i-1]) { min = pre[i-1] + 1; } else { max = pre[i-1] - 1; } } // return false if the current element in the preorder sequence // is not in a valid range else { return false; } } return true; } public static void main(String[] args) { int[] pre = { 15, 30, 25, 18, 20 }; boolean isSkewed = isSkewedBST(pre); if (isSkewed) { System.out.println("BST is skewed"); } else { System.out.println("BST is not skewed"); } } } |
Output:
BST is skewed
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
import sys # Function to determine whether the given preorder traversal of a binary tree # represents a skewed BST def isSkewedBST(pre): # initialize the range (min, max) with (-INF, INF) min = -sys.maxsize max = sys.maxsize # start from the second element in the preorder sequence for i in range(1, len(pre)): # if the current element is in a valid range if min <= pre[i] <= max: # update a valid range for the next element in the preorder sequence if pre[i] > pre[i - 1]: min = pre[i - 1] + 1 else: max = pre[i - 1] - 1 # return false if the current element in the preorder sequence is not in a # valid range else: return False return True if __name__ == '__main__': pre = [15, 30, 25, 18, 20] if isSkewedBST(pre): print('BST is skewed') else: print('BST is not skewed') |
Output:
BST is skewed
The time complexity of the above solutions is O(n) and doesn’t require any extra space.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)