Validate a Binary Search Tree

Validate a Binary Search Tree

Determine whether a given binary tree satisfies the BST property.

Input format

The first line contains level-order tokens, where N denotes a null node.

Output format

Print true if the tree is a valid BST, false otherwise.

Constraints

• Values fit in a 64-bit signed integer
• Trailing whitespace and a trailing newline are ignored by the judge

Read from stdin, write to stdout. Sample cases below show the exact format.

84 49 N 12 57 N 46 53 83 N N N N 58

true

45 18 57 1 42 N 71 N 4 25 N 66 74 2 5 N 38 64 N N 97 N N N 13 30 N N N 90 N N N N N 84 N 77

true