Check Binary Search Tree

You are given a binary tree represented as a list of nodes. Each node is described by three integers: the node's value, the index of its left child, and the index of its right child. An index of -1 indicates that the respective child does not exist. The nodes are given in 0-indexed order, and the tree is rooted at the node with index 0.

A binary tree is a valid Binary Search Tree (BST) if for every node with value \(v\), all values in its left subtree are strictly less than \(v\) and all values in its right subtree are strictly greater than \(v\). Formally, for every node, the following invariant must hold: $$min < \text{node.value} < max$$ where the valid range \((min, max)\) is updated as you traverse the tree. If the tree is empty, consider it a BST.

Your task is to determine whether the given binary tree is a BST. Print "YES" if it is a BST, or "NO" otherwise.

inputFormat

The input is given via standard input (stdin). The first line contains an integer \(n\) representing the number of nodes in the tree. If \(n = 0\), the tree is empty. Each of the following \(n\) lines contains three space-separated integers: value left_child_index right_child_index. A value of -1 for left_child_index or right_child_index indicates that the child does not exist.

outputFormat

Output a single line to standard output (stdout) containing either "YES" if the binary tree is a binary search tree, or "NO" otherwise.

1
10 -1 -1

YES