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.

BST

 
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:

 

Download   Run Code

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++:

 

Download   Run Code

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.

 
1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of