fork download
  1. import java.util.*;
  2.  
  3. class Main{
  4. static boolean preorderBST(int input[], int n)
  5. {
  6. Stack<Integer> s = new Stack<Integer>();
  7. int root = Integer.MIN_VALUE;
  8. for(int i=0;i<n;i++)
  9. {
  10. // if current node is smaller than the root
  11. // the current node lies on the right of root
  12. // thus it is impossible for bst
  13. if (input[i] < root)
  14. return false;
  15. // keep removing elements smaller than the root
  16. // until you find an element which is greater than the root
  17. while(!s.empty() && s.peek()<input[i]){
  18. root = s.peek();
  19. s.pop();
  20. }
  21. // if current element is smaller than the root
  22. // push it into stack
  23. s.push(input[i]);
  24. }
  25. // if we passed until the end of the array
  26. // that means that the given preorder sequence represents a valid BST
  27. return true;
  28. }
  29.  
  30. public static void main(String[] args)
  31. {
  32. int input[] = {5, 3, 4, 7, 6, 9, 8, 11};
  33. int n = input.length;
  34.  
  35. System.out.print((preorderBST(input, n)) ? "yes" : "no");
  36. }
  37. }
Success #stdin #stdout 0.06s 32352KB
stdin
Standard input is empty
stdout
yes