How should I practice Validate a BST with a Custom Comparison?

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

Is Validate a BST with a Custom Comparison associated with Apple?

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

Validate a BST with a Custom Comparison

Apple● MediumFULLTIMEPHONE SCREEN

Problem statement

You are given a binary tree whose node values are labels of an unknown type. You can't compare two labels by their spelling. The only comparison you may use is the one you are given: label a is smaller than label b when a comes before b in the list order.

The tree has n nodes numbered 0 to n - 1, and node 0 is the root. Node i has the label values[i]. Its left child is node left[i] and its right child is node right[i]. A value of -1 means there is no child.

Return true if the tree is a valid binary search tree under this comparison, and false otherwise. The tree is valid when, for every node:

every label in its left subtree is strictly smaller than the node's label, and
every label in its right subtree is strictly larger than the node's label.

Because both rules are strict, a valid tree never contains the same label twice.

Function

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

Examples

Example 1

values = ["apple","kiwi","mango"]left = [1,-1,-1]right = [2,-1,-1]order = ["kiwi","apple","mango"]return = true

In order, kiwi comes before apple, and apple comes before mango. So the left child kiwi is smaller than the root and the right child mango is larger. The tree is valid, even though kiwi comes after apple in alphabetical order.

Example 2

values = ["echo","alpha","bravo"]left = [1,-1,-1]right = [-1,2,-1]order = ["delta","alpha","echo","bravo","charlie"]return = false

Node 2 (bravo) is the right child of alpha, and alpha comes before bravo in order, so that link is fine. But bravo is also in the left subtree of the root echo, and bravo comes after echo in order. The tree is not valid.

Example 3

values = ["moon","moon"]left = [1,-1]right = [-1,-1]order = ["sun","moon"]return = false

The root and its left child have the same label. A left child must be strictly smaller, so the tree is not valid.

Constraints

1 <= values.length <= 500
left.length == right.length == values.length
-1 <= left[i], right[i] <= values.length - 1
Node 0 is the root. The links form one binary tree: every other node is the child of exactly one node, and every node can be reached from node 0.
1 <= order.length <= 1000
The labels in order are all different.
Every label in values appears in order.
Every label has 1 to 8 lowercase English letters.