Is it a valid search tree

Scenario

An online shop keeps the prices of its items in a binary search tree, so that its price filter can find a price quickly. The rule of the tree applies at every node. Every price in the left subtree is lower than the node's price, and every price in the right subtree is higher. No two items have the same price.

After a bad import, you suspect that the tree is broken. The tree can hold up to 100,000 prices.

Your task

Write is_valid_price_tree(values, left, right).

The nodes are numbered 0 to n - 1, and node 0 is the root.
values[i] is the price in node i.
left[i] and right[i] are the numbers of the left and right children of node i, or -1 where there is none.
Return true if the tree follows the rule at every node, and false otherwise.

Examples

Example 1 (traced)#

text2 lines

Input:  values = [40, 25, 60, 10, 30, 50, 70], left = [1, 3, 5, -1, -1, -1, -1], right = [2, 4, 6, -1, -1, -1, -1]
Output: true

Node	Price	Allowed range (low, high)	Inside?
0	40	no limits	yes
2	60	above 40	yes
1	25	below 40	yes
4	30	above 25 and below 40	yes
3	10	below 25	yes
6	70	above 60	yes
5	50	above 40 and below 60	yes

Every price is inside the range its position allows.

Example 2#

text2 lines

Input:  values = [40, 25, 60, 10, 30, 55], left = [1, 3, -1, -1, -1, -1], right = [2, 4, -1, -1, 5, -1]
Output: false

Every child agrees with its parent: 25 is below 40, 30 is above 25, and 55 is above 30. But 55 sits in the left subtree of 40, so it must be below 40.

Example 3#

text2 lines

Input:  values = [5, 5], left = [1, -1], right = [-1, -1]
Output: false

The left child must be strictly lower, and an equal price is not lower.

Constraints

1 ≤ length of values = length of left = length of right ≤ 10^5
1 ≤ values[i] ≤ 10^6
every entry of left and right is -1 or a node number from 1 to n - 1
the nodes form one tree under node 0

What does n ≤ 10^5 tell you?

A tree that is a chain of 100,000 nodes is allowed. Checking every node against everything in its subtree costs the size of the subtree for each node, which is about 5 × 10^9 steps for a chain.

A function that calls itself for each child needs 100,000 nested calls on a chain, and many languages stop long before that. Use a loop with a stack.

Scenario

After a bad import, you suspect that the tree is broken. The tree can hold up to 100,000 prices.

Your task

Write is_valid_price_tree(values, left, right).

The nodes are numbered 0 to n - 1, and node 0 is the root.
values[i] is the price in node i.
left[i] and right[i] are the numbers of the left and right children of node i, or -1 where there is none.
Return true if the tree follows the rule at every node, and false otherwise.

Examples

Example 1 (traced)#

text2 lines

Input:  values = [40, 25, 60, 10, 30, 50, 70], left = [1, 3, 5, -1, -1, -1, -1], right = [2, 4, 6, -1, -1, -1, -1]
Output: true

Node	Price	Allowed range (low, high)	Inside?
0	40	no limits	yes
2	60	above 40	yes
1	25	below 40	yes
4	30	above 25 and below 40	yes
3	10	below 25	yes
6	70	above 60	yes
5	50	above 40 and below 60	yes

Every price is inside the range its position allows.

Example 2#

text2 lines

Input:  values = [40, 25, 60, 10, 30, 55], left = [1, 3, -1, -1, -1, -1], right = [2, 4, -1, -1, 5, -1]
Output: false

Every child agrees with its parent: 25 is below 40, 30 is above 25, and 55 is above 30. But 55 sits in the left subtree of 40, so it must be below 40.

Example 3#

text2 lines

Input:  values = [5, 5], left = [1, -1], right = [-1, -1]
Output: false

The left child must be strictly lower, and an equal price is not lower.

Constraints

1 ≤ length of values = length of left = length of right ≤ 10^5
1 ≤ values[i] ≤ 10^6
every entry of left and right is -1 or a node number from 1 to n - 1
the nodes form one tree under node 0

What does n ≤ 10^5 tell you?

A tree that is a chain of 100,000 nodes is allowed. Checking every node against everything in its subtree costs the size of the subtree for each node, which is about 5 × 10^9 steps for a chain.

A function that calls itself for each child needs 100,000 nested calls on a chain, and many languages stop long before that. Use a loop with a stack.