Verify Preorder Sequence Of Binary Search Tree(BST)

Check if a given array can represent Preorder Traversal of Binary Search Tree. OR
Check if given Preorder traversal is valid BST (Binary Search Tree). OR
Given an array of numbers, verify whether it is the correct Preorder traversal sequence of a binary search tree.

---

You are given an array of numbers which represents Preorder traversal of Binary Search Tree.
Verify whether it is a correct Preorder sequence or not.

Lets understand what is the input and the expected output.

Input: [40, 30, 35, 20, 80, 100] Output: Invalid Preorder traversal
 
Input: [45, 25, 15, 35, 75]
Output: Valid Preorder traversal

Input: [50, 39, 44, 28, 85]
Output: Invalid Preorder traversal
 
Input: [10, 25, 5]
Output: Invalid Preorder traversal
 

Input: [30, 20, 10, 40, 50]
Output: Valid Preorder traversal

Algorithm

---

Lets see how to verify whether given array represents valid preorder traversal of a Binary Search Tree or not.

Approach 1

In this approach, We will use property of BST but without creating BST.

Preorder traversal of BST will always have,
1. Root element first followed by 
2. Left sub-tree followed by 
3. Right sub-tree.


So for identifying whether the given Preorder traversal is valid sequence of BST,
For each node(A), we will first identify the start of Right sub-tree and then check all element after start of Right sub tree should be greater than A. If we found any element less than A then it is not valid Preorder sequence.

So from above example, we will first work for Root Node 45.
Start of Right sub-tree, that is first element greater than 45 is Node 75, So all values after Node 75 should be greater than 45. There is no element present.
So given Preorder sequence considering Node 45 is correct.

Now, we will work on next Node 25. Now for Node 25, we don't need to check element beyond 75 because it is already checked in above iteration and it is satisfying that is why we reached this iteration. 
(For Node 25, the Left subtree is 15 and Right subtree is 35.)
So for Node 25, we will find the first greater element than 25 uptil 75(beyond this is already checked)
Which is 35. So  start of Right subtree is 35 and all elements between 35 and 75 should be greater than 25. It means it satisfies our property.

Now, we will work on next Node 15. Now for Node 15, we don't need to check element beyond 35 because it is already checked in above iteration and it is satisfying that is why we reached this iteration. 
(For Node 15, the Left subtree is empty and Right subtree is empty.)
So for Node 15, we will find the first greater element than 15 uptil 35(beyond this is already checked)
No node present. It means it satisfies our property.

We did this check for Left sub-tree, Similar check we need to do for Right sub-tree of Root node 45.
If the above property satisfies for all the nodes than the given Preorder traversal is valid traversal sequence of BST.

So to summarize the above steps we can say,

For every element Preorder[i], i=0 to n. Find the first greater value(start of Right sub-tree) than current node. Let the index at which first greater element found be j. 
Return True if following conditions satisfies else return False,
1.  All values after the above found greater element  are greater than current node.
2.  Recursively calls for the sub-arrays Preorder[ i+1 ... j-1 ] and Preorder[ j+1 ... n-1 ], 
     So that all elements are covered and return true if they also satisfies point 1.

This method requires O(N^2) time complexity to check Preorder sequence is valid or not.

package javabypatel;

public class VerifyPreorderSequenceInBinarySearchTree {

 public static void main(String[] args) {
  new VerifyPreorderSequenceInBinarySearchTree();
 }
 
 public VerifyPreorderSequenceInBinarySearchTree() {
  int[] preOrderTraversal = {30, 20, 10, 40, 50};
  System.out.println(isValid(preOrderTraversal, 0, preOrderTraversal.length-1, Integer.MIN_VALUE, Integer.MAX_VALUE));
 }

 public static boolean isValid(int arr[], int start, int end, int min, int max){
  if(start>=end){
   return true;
  }
  
  int root = arr[start];
  
  //Find Max index
  int maxIndex = start;
  for (int i = start; i <= end; i++) {
   if(arr[i] < min || arr[i] > max){
    return false;
   }
   if(arr[i] > root){
    break;
   }
   maxIndex++;
  }

  
  boolean left = isValid(arr, start+1, maxIndex-1, min, arr[start]-1);  
  //arr[start]-1 because for next recursive call, max should be one less(on Left side)  as we are assuming BST doesn't contain duplicates 
  
  boolean right = isValid(arr, maxIndex, end, arr[start]+1, max);
  //arr[start]+1 because for next recursive call, min should be one more(on Right side) as we are assuming BST doesn't contain duplicates
  
  return left && right;
 }
}

Can we solve it in O(N)? Lets see..

Approach 2

---

In this approach, we will use 2 Stacks. 

Stack 1 will hold Preorder values. It means stack will grow in ascending order.
Bottom of the stack will have largest value and on top will be smallest.

Stack 2 will hold Inorder values. It means stack will grow in descending order.
Bottom of the stack will have smallest value and on top will be largest.

We will start reading given Preorder traversal from i=0 to n.

We already saw that Root Node will be first in Preorder traversal followed by Left sub-tree elements followed by Right sub-tree elements.

So if the given Preorder traversal is a valid traversal sequence of BST then you will encounter 
1. Highest element first, followed by
2. All smaller elements(Left sub-tree) compared to first element, followed by
3. All higher elements(Right sub-tree) compared to first element.


We will validate the given Preorder traversal is a valid traversal sequence of BST by using above 2 stacks.

Start reading given Preorder traversal and put elements into Stack 1.
While putting elements to Stack 1, make sure that element at top of the stack is larger that current element i.
As soon as you encounter current element i is greater than element at top of stack, Stop here and 
start popping the element from stack until you find the elements greater than current element i and put the current element i on top of Stack 1.

Push the poped elements from Stack 1 to Stack 2 which is holding values in Inorder fashion.
(Stack 2 will always have element at top higher than below elements.)

As soon as you find that element pushed to Stack 2 is smaller than the element present on top of Stack 2. Stop here, because this happens only when given Preorder traversal is INVALID traversal sequence of BST otherwise pushed element from Stack 1 will always be the greater element than element present on top of Stack 2.

Lets understand it with the help of both Valid and Invalid scenario example.

Valid example.


Invalid Example.


We are using Stack in these approach which is wastage of memory, can we save this memory and solve it in constant space. Lets see.

Approach 3

---

In this approach we will try to save the extra memory we used in Approach 3.

Inorder stack(Stack 2) that we used for storing values is no where used in the program except the element at the top of the stack which is used to compare it with the new element to be placed on top of it.

So instead of taking stack we can use some variable say "topElementAtInorderStack", that will hold the value at the top of Inorder stack and we will compare the value to be placed on top of the stack with this variable.

If the value to be placed on top of Stack 2 is LARGER than variable topElementAtInorderStack, then we will update topElementAtInorderStack to hold new value.

If the value to be placed on top of Stack 2 is SMALLER than variable topElementAtInorderStack, then we will Stop our execution because it says that given Preorder traversal is INVALID traversal sequence of BST.

Java Program to check if a given array can represent Preorder Traversal of Binary Search Tree

---

package javabypatel;

import java.util.Stack;

public class VerifyPreorderSequenceInBinarySearchTree {

 public static void main(String[] args) {
  new VerifyPreorderSequenceInBinarySearchTree();
 }

 public VerifyPreorderSequenceInBinarySearchTree() {
  int[] preOrderTraversal = {40, 30, 35, 20, 80, 100};
  
  boolean flag = checkPreorderCanRepresentBST(preOrderTraversal);
  
  if(flag){
   System.out.println("Valid Preorder traversal");
  }else{
   System.out.println("Invalid Preorder traversal");
  }
 }

 private static boolean checkPreorderCanRepresentBST(int[] preOrderTraversal){
  
  //Stack for holding elements in Preorder fashion.
  Stack<Integer> stack = new Stack<Integer>();
  
  //Instead of Stack, we are taking variable which will hold last value at top of Inorder stack.
  //initializing it to Integer.MIN_VALUE, So that next value should be greater than this atleast.
  int lastInOrderNumber = Integer.MIN_VALUE;

  for (int i=0; i<preOrderTraversal.length; i++) {
   int data = preOrderTraversal[i];

   //If any value we encounter which is less than already stored last value in Inorder stack(lastInOrderNumber), return false.
   //If the value coming in is less it means preorder is not valid otherwise it will always be in increasing order.
   if(data < lastInOrderNumber){
    return false;
   }

   //If the Preorder stack peek contains element which is smaller than current working data,
   //then pop till you find element greater than current working data.
   //also mark last poped data as lastInOrderNumber.
   while(!stack.isEmpty() && stack.peek() < data ){
    lastInOrderNumber = stack.peek();
    stack.pop();
   }
   stack.add(data);
  }
  return true;
 }

}

You may also like to see

---

Top Binary tree interview questions in Java

Find Kth SMALLEST element in BST(Binary Search Tree)

Check whether Binary Tree is foldable or not.

Check if two nodes are cousins in a Binary Tree.

Get Level/Height of node in binary tree

Print nodes at K distance from Leaf node in Binary tree.

Construct a Binary Tree from In-order and Post-order traversals.

Print Nodes in Top View of Binary Tree.

Zig Zag Traversal of Binary Tree.