Challenge: Is It a Valid BST?

Lab Python Intermediate 20 points

The input is a binary tree in level order (N = no node). Print valid if it follows the BST rule (all values in a left subtree are smaller, all in a right subtree are bigger), otherwise invalid. Careful: checking each node only against its direct children isn't enough!

Input

One line: level-order values with N for missing nodes.

Output

valid or invalid.

Example

Input

8 3 10 1 6 N 14

Output

valid

Sample input available Sample output available

Editor

Python

Hints

Pass down the allowed range (low, high) for each node.

Going left, the node's value becomes the new high; going right, it becomes the new low.

Solution explanation

In 10 5 15 N N 6 20, the 6 is the left child of 15, so it looks fine next to its parent. But it sits in 10's right subtree, so it must be bigger than 10. Passing the allowed range down catches this.

Show solution

from collections import deque


class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


def build(tokens):
    if not tokens or tokens[0] == "N":
        return None
    root = Node(int(tokens[0]))
    q = deque([root])
    i = 1
    while q and i < len(tokens):
        node = q.popleft()
        if tokens[i] != "N":
            node.left = Node(int(tokens[i]))
            q.append(node.left)
        i += 1
        if i < len(tokens) and tokens[i] != "N":
            node.right = Node(int(tokens[i]))
            q.append(node.right)
        i += 1
    return root


def ok(n, low, high):
    if n is None:
        return True
    if not (low < n.value < high):
        return False
    return ok(n.left, low, n.value) and ok(n.right, n.value, high)


root = build(input().split())
print("valid" if ok(root, float("-inf"), float("inf")) else "invalid")

Output

Answer