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 inorder_BST() 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 inorder_BST() function is an integer array and its length. The following is an example input:

[8,12,15,21,24,32,45]

Output

The following is the output of the inorder_BST() function, in case it fulfills the condition:

True

Otherwise, it outputs the following:

False

Coding exercise

Implement the inorder_BST(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.