Binary Search Tree (BST)

A Binary Search Tree (BST) is a special type of binary tree that follows two properties:

All the left child nodes have a smaller value than their parent node

All the right child nodes have greater value than their parent node

So, for each node, it either misses a child node or has a smaller node on the left and a larger node on the right.

This property is especially useful for searching elements in a binary tree. If we’re looking for a value x, this way we always know which way to go to find that value. In the example presented above, to find the node with value 3, we can first look at the root node with value 5. As 5 is greater than 3, we move left. We then look at the node with the value 2, and as 2 is smaller than 3, we move right. We then look at the node with the value 4, and as 4 is greater than 3, we move left. We then look at the node with the value 3, and as 3 is equal to 3, it means that we found the node.

# Assume that non-existing nodes are None instead of having a value of 0
def search(node: Node | None, x: int):
    """ Return True if `x` is present in the tree and False otherwise """
    if node is None:              # If we've reached the end of the tree
        return False              # We didn't find the value `x`
    if x == node.value:           # If `x` is equal to `node.value`
        return True               # => we found the value `x` in the tree

    if x < node.value:            # If `x` is smaller => we need to move left
        return search(node.left)  # Try to find `x` in the left subtree
    return search(node.right)     # Otherwise try finding `x` in the right one

This way of searching can be very efficient if the height of the tree is small enough. On each iteration we either move to the left or the right subtree, so searching in this binary search tree would result in the number of operations being equivalent to the height of the tree in the worst-case scenario.

Challenge: Check if the given tree is a BST

Given a binary tree, you are asked to check if it’s a binary search tree.

Input

The input contains space-separated integers representing the values in the nodes of the binary tree. The order of the values is given by traversing from the left to the right subtree every time. A value of 0 means that the node does not exist. It’s guaranteed that the input binary tree is valid and the values are unique.

Output

The program should print Yes if the binary tree is a binary search tree, and No otherwise.

Examples

Input	Output
1 2 3 8 5 0 0 0 0 5 8 0 0 0 0	No
5 2 7 1 4 0 0 3 0 0 0 6 8 0 0 0 0	Yes

Explanation

Example 1: Even though all the right child nodes are greater than the parent nodes, not all left children are smaller than their parent.

Example 2: It’s a binary tree as all the left child nodes have smaller values than their parent, while all the right child nodes have a greater value than their parent.

Constraints

Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB