Validate BST

Problem statement

A lookup service stores records in a proposed binary search tree. Before using ordered lookup, an audit must ensure that every descendant obeys its ancestors' bounds, not merely that each immediate child looks correctly placed. Your task Determine whether the tree is a valid binary search tree: all values in each node's left subtree are strictly smaller, and all values in its right subtree are strictly larger. Important details Duplicate values are invalid. The rule applies to whole subtrees, so a value may violate a grandparent's bound despite fitting beside its own parent. An empty tree is valid. Worked example Root 5 with left child 3 and right child 7 is valid. If node 7 has left child 4, that 4 lies in the right subtree of 5 and makes the tree invalid.

Input format

The first line contains n. The next n lines contain value left right for nodes 0 through n-1. Child indices are -1 when absent. Node 0 is the root when n > 0. The records form one valid binary tree; n = 0 represents an empty tree.

Output format

Print true if the condition holds, otherwise false.

Constraints

0 <= n <= 2000; -1000 <= value <= 1000. Child indices are -1 or valid node indices; no cycles or shared children.

Sample input

3
5 1 2
3 -1 -1
7 -1 -1

Sample output

true