Loading...
Loading...
Loading...
Sneha's lab partner wrote a program that should store numbers in a binary search tree, but she suspects a bug. She prints the tree and wants to check it.
A tree is a valid binary search tree when, for every node, all values in its left subtree are smaller than it and all values in its right subtree are larger. Equal values are not allowed. Print YES if the given tree is valid, otherwise NO. An empty tree is valid.
N for no node. Children are listed only for real nodes, and N tokens at the end of the line may be left out. For example, 5 3 8 N 4 N N N N is 5 with children 3 and 8, and 3 has right child 4. An empty tree is N.YES or NO.int range)Example 1
Input
5 3 8 N 4 N N N N
Output
YES
3 and 4 are below 5, 8 is above it, and 4 is above 3. Every rule holds.
Example 2
Input
5 3 8 N 6 N N N N
Output
NO
6 is a right child of 3, which is fine locally. But 6 is in the left subtree of 5 and is larger than 5.
Try the problem first. Open one hint at a time.
Comparing a node only with its own children is not enough. Look at the second sample.
Each node has an allowed range: above every ancestor it is right of, and below every ancestor it is left of.
Pass the range down: going left, the node becomes the new upper bound; going right, the new lower bound.
Values can be the exact int limits, so keep the bounds in a long or use "no bound yet" for the start.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor