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

Bubble Sort

Bubble Sort (Sinking sort)

---

Given a array of integers, Sort it.
Lets understand what is the input and the expected output.

Insertion Sort

Insertion Sort

---

Given a array of integers, Sort it using Insertion sort. Lets understand what is the input and the expected output.

Selection Sort

Selection Sort

---

Given a array of integers, Sort it.
Lets understand what is the input and the expected output.

Infinite loop in HashMap

Why HashMap should not be used in multi threaded environment?
Can it cause infinite loop as well?
When get method go to infinite loop in HashMap?

---

If HashMap is used in Multi threading environment, there are chances that Get and Put operation can lead you to Infinite loop.