Verify preorder sequence of Binary Search Tree (BST) Interview Question – Hacker Rank

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:

  1. 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]
  2. 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.
  3. 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”.

  4. 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:
ProjectStructure

Code is as below:

Output:

Below is the same code as above, with Hacker Rank Input style:

Input/Output Pattern:

You can have above code from GIT.

GitHub-Mark-32px https://github.com/Niravkumar-Patel/SnippetExampleRepo.git


Leave a Reply

Your email address will not be published. Required fields are marked *