BST Validation Challenge

You are given a description of a binary tree. The first line of the input contains an integer n (n ≥ 0) representing the number of nodes in the tree. Each of the next n lines contains three values separated by spaces: val left right. Here, val is an integer representing the node's value, and left and right represent the values of the left and right children, respectively. If a child is absent, the value will be given as None. The tree is constructed in the order given (the first node is the root). Your task is to determine whether the given tree is a valid Binary Search Tree (BST).

A BST is defined as follows: For each node with value v, all values in its left subtree must be strictly less than v, and all values in its right subtree must be strictly greater than v. Formally, a binary tree is a BST if for every node, the following condition holds: $$\textit{left} < v < \textit{right}$$ where the bounds are appropriately updated as you traverse the tree.

inputFormat

The input is read from standard input (stdin) and has the following format:

n
val1 left1 right1
val2 left2 right2
... 
valn leftn rightn

If n is 0, the tree is considered empty.

outputFormat

Output a single line to standard output (stdout) containing YES if the tree is a valid BST, and NO otherwise.

9
8 3 10
3 1 6
1 None None
6 4 7
4 None None
7 None None
10 None 14
14 13 None
13 None None

YES