DIY: Validate the Binary Search Tree

Solve the interview question "Validate the Binary Search Tree" in this lesson.

Problem statement

For this challenge, you are given an integer array. You have to implement the InOrderBST() function to validate whether the given integer array represents the in-order traversal of a valid binary search tree

Constraints

  • Nodes count of the binary search tree in the range [1, 10410^4].
  • 231-2^{31} <= Node.value <= 2312^{31} - 1

Input

The input of the InOrderBST() function is an integer array and its length. The following is an example input:

// Sample Example 1
[8,12,15,21,24,32,45]

// Sample Example 2
[3, 22, 34, 41, 52, 45]

Output

The following is the output of the InOrderBST() function for the above inputs:

// Sample Example 1
true

// Sample Example 2
false

Coding exercise

Implement the InOrderBST(array,n) function, where array is an integer array that represents the in-order traversal of a binary search tree, and n is the given array’s length.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.