Goal: Verify pre order sequence of Binary Search Tree (BST)
Problem:
You have an array of preorder traversal of Binary Search Tree ( BST). Your program should verify whether it is a correct sequence or not.
Input: Array of Integer [ Pre-order BST ] Output: String “Yes” or “No”
To solve above problem, you do not need to construct a Binary Tree from a given pre-order sequence.
The pre-order sequence of binary tree can form a sorted stack. So lets break it in a few “SIMPLE” steps as follows:
Iterate over each element and follow the steps below:
- Push to stack till you get higher element than the topmost element of the stack. [i.e. you keep pushing till you hit the leftmost leaf]
- If you find the current value which is greater than the TOP of Stack, POP till you hit higher element and also mark the last popped value, which is your variable (Left_Tree_Highest). This variable is used to check whether the order is correct or not.
- In all the steps, if you find current element lesser than Left_Tree_Highest, then your tree is not a Binary Search Tree and it should return “NO”.
-
If all the element traversed, and you have not hit “NO”, means given sequence follows the Binary Search Tree rule.
Above step might be confusing, but take a pen and paper, try to follow the steps by taking stacks and Left_Tree_Highest values at each step. Once you are able to track it, you will able to correlate it with the steps given above.
So the basic idea is that at any point, left subtree’s highest element should be lowest for the untraversed elements [Right Tree].
Below is the project structure and code for the same:
Code is as below:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
import java.util.Stack; public class PreorderBST { public static void main(String args[]){ int[] inputPreOrderArray = {1,2,3}; System.out.println(checkBST(inputPreOrderArray)); int[] inputPreOrderArray1 = {3,2,1,5,4,6}; System.out.println(checkBST(inputPreOrderArray1)); int[] inputPreOrderArray2 = {3,4,5,1,2}; System.out.println(checkBST(inputPreOrderArray2)); } public static String checkBST(int[] inOrderArray){ Stack<Integer> s = new Stack<Integer>(); int lower = -1; for(int i=0;i<inOrderArray.length;i++){ if(lower>-1 && inOrderArray[i] < lower){ return "NO"; } while(!s.isEmpty() && s.peek()<inOrderArray[i]){ lower = s.pop(); } s.push(inOrderArray[i]); } return "YES"; } } |
Output:
|
1 2 3 4 5 6 7 8 9 |
For input: 1,2,3 3,2,1,5,4,6 3,4,5,1,2 Output: YES YES NO |
Below is the same code as above, with Hacker Rank Input style:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
import java.util.ArrayList; import java.util.Scanner; import java.util.Stack; public class PreorderBST { public static void main(String args[]){ Scanner in = new Scanner(System.in); int testCaseNumber = Integer.parseInt(in.nextLine()); ArrayList<String> output = new ArrayList<String>(); while(testCaseNumber>0){ int size = Integer.parseInt(in.nextLine()); int[] preOrderArray = new int[size]; String[] numberStrArray = in.nextLine().split(" "); for(int i=0;i<numberStrArray.length;i++){ preOrderArray[i] = Integer.parseInt(numberStrArray[i]); } output.add(checkBST(preOrderArray)); testCaseNumber--; } for(int i=0;i<output.size();i++){ System.out.println(output.get(i)); } in.close(); } public static String checkBST(int[] inOrderArray){ Stack<Integer> s = new Stack<Integer>(); int lower = -1; for(int i=0;i<inOrderArray.length;i++){ if(lower>-1 && inOrderArray[i] < lower){ return "NO"; } while(!s.isEmpty() && s.peek()<inOrderArray[i]){ lower = s.pop(); } s.push(inOrderArray[i]); } return "YES"; } } |
Input/Output Pattern:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
3 //Number of test case 3 //Number of Element for test case 1 1 2 3 6 //Number of Element for test case 2 3 2 1 5 4 6 5 //Number of Element for test case 3 3 4 5 1 2 Output: YES YES NO |
You can have above code from GIT.
https://github.com/Niravkumar-Patel/SnippetExampleRepo.git