# Check if a given sequence represents preorder traversal of a BST

Given a distinct sequence of keys, check if it can represent a preorder traversal of a binary search tree (BST).

For example, below BST can be constructed from sequence { 15, 10, 8, 12, 20, 16, 25 } and it has the same preorder traversal.

The idea is to first construct a BST from the given sequence by inserting keys into the BST one at a time. Next we compare the preorder traversal of the constructed BST with the given sequence. If the order matches, we can say that the given sequence represents preorder traversal of a BST. Here’s a C++ program that demonstrates it:

Output:

Given sequence represents preorder traversal of a BST

The time complexity of above solution is O(nlog(n)) and takes O(n) extra space for the call stack. We can reduce the time complexity to O(n) by constructing a BST from the given sequence in preorder fashion. Now the problem reduces to just validating if the whole sequence was traversed or not while constructing the BST. If the whole sequence is traversed, we can say that the given sequence represents preorder traversal of a BST. This is demonstrated below in C++:

Output:

Given sequence represents preorder traversal of a BST

The time complexity of above solution is O(n) and takes O(n) extra space for the call stack.

(2 votes, average: 5.00 out of 5)