Check if a given array can represent Preorder Traversal of Binary Search Tree - GeeksforGeeks

Check if a given array can represent Preorder Traversal of Binary Search Tree - GeeksforGeeks

Check if a given array can represent Preorder Traversal of Binary Search Tree

Given an array of numbers, return true if given array can represent preorder traversal of a Binary Search Tree, else return false. Expected time complexity is O(n).

Examples:

Input:  pre[] = {2, 4, 3}  Output: true  Given array can represent preorder traversal  of below tree      2       \        4       /      3    Input:  pre[] = {2, 4, 1}  Output: false  Given array cannot represent preorder traversal  of a Binary Search Tree.    Input:  pre[] = {40, 30, 35, 80, 100}  Output: true  Given array can represent preorder traversal  of below tree       40     /   \   30    80     \      \    35     100       Input:  pre[] = {40, 30, 35, 20, 80, 100}  Output: false  Given array cannot represent preorder traversal  of a Binary Search Tree.  

We strongly recommend you to minimize your browser and try this yourself first.

A Simple Solution is to do following for every node pre[i] starting from first one.

1) Find the first greater value on right side of current node.      Let the index of this node be j. Return true if following      conditions hold. Else return false      (i)  All values after the above found greater value are            greater than current node.      (ii) Recursive calls for the subarrays pre[i+1..j-1] and            pre[j+1..n-1] also return true. 

Time Complexity of the above solution is O(n²)

An Efficient Solution can solve this problem in O(n) time. The idea is to use a stack. This problem is similar to Next (or closest) Greater Element problem. Here we find next greater element and after finding next greater, if we find a smaller element, then return false.

1) Create an empty stack.  2) Initialize root as INT_MIN.  3) Do following for every element pre[i]       a) If pre[i] is greater than current root, return false.       b) Keep removing elements from stack while pre[i] is greater          then stack top. Make the last removed item as new root (to          be compared next).          At this point, pre[i] is greater than the removed root          (That is why if we see a smaller element in step a), we           return false)       c) push pre[i] to stack (All elements in stack are in decreasing          order)  

Read full article from Check if a given array can represent Preorder Traversal of Binary Search Tree - GeeksforGeeks