How should I practice Validate Binary Search Tree?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Lyft phone screen problems in FastPrep.

Is Validate Binary Search Tree associated with Lyft?

FastPrep tags this as a Lyft phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Tree

Validate Binary Search Tree

Learn this problem

● Medium

LyftFULLTIMEPHONE SCREEN

Problem statement

A binary tree is represented by aligned arrays. Node i has value values[i]; left[i] and right[i] contain child indices, or -1 when that child is absent. The index root identifies the root node.

Return true if the tree is a valid binary search tree and false otherwise.

For every node, every value in its left subtree must be strictly smaller and every value in its right subtree must be strictly greater. Therefore duplicate values make the tree invalid.

Function

isValidBST(values: int[], left: int[], right: int[], root: int) → boolean

Examples

Example 1

values = [2,1,3]left = [1,-1,-1]right = [2,-1,-1]root = 0return = true

The left value 1 is smaller than 2, and the right value 3 is greater.

Example 2

values = [5,1,4,3,6]left = [1,-1,3,-1,-1]right = [2,-1,4,-1,-1]root = 0return = false

Node value 4 lies in the right subtree of 5 but is not greater than 5.

Constraints

0 <= values.length <= 1000.
left.length = right.length = values.length.
Node values are unique signed 32-bit integers.
Child entries are -1 or valid node indices, and the arrays describe one finite binary tree.
root = -1 exactly when the tree is empty; otherwise it is a valid node index.