given the root of a binary tree determine if it is a valid binary search tree bst a valid binary search tree is defined as follows the left subtree of a node contains only nodes with keys less than the node s key the right subtree of a node contains only nodes with keys greater than the node s key both the left and right subtrees must also be binary search trees in effect a binary tree is a valid bst if its nodes are sorted in ascending order leetcode https leetcode comproblemsvalidatebinarysearchtree if n is the number of nodes in the tree then runtime on space o1 root nodedata2 1 listroot 2 1 root leftnodedata2 0 listroot 2 0 2 1 root rightnodedata2 2 listroot 2 0 2 1 2 2 nodedata abc issorted true nodedata2 leftnodedata1 999 rightnodedata3 issorted true nodedata0 leftnodedata0 rightnodedata0 issorted true nodedata0 leftnodedata11 rightnodedata3 issorted true nodedata5 leftnodedata1 rightnodedata4 leftnodedata3 issorted false nodedata a leftnodedata1 rightnodedata4 leftnodedata3 issorted traceback most recent call last typeerror not supported between instances of str and int nodedata2 leftnode rightnodedata4 leftnodedata3 issorted traceback most recent call last typeerror not supported between instances of int and list root node data 2 1 list root 2 1 root left node data 2 0 list root 2 0 2 1 root right node data 2 2 list root 2 0 2 1 2 2 node data abc is_sorted true node data 2 left node data 1 999 right node data 3 is_sorted true node data 0 left node data 0 right node data 0 is_sorted true node data 0 left node data 11 right node data 3 is_sorted true node data 5 left node data 1 right node data 4 left node data 3 is_sorted false node data a left node data 1 right node data 4 left node data 3 is_sorted traceback most recent call last typeerror not supported between instances of str and int node data 2 left node right node data 4 left node data 3 is_sorted traceback most recent call last typeerror not supported between instances of int and list
from __future__ import annotations

from collections.abc import Iterator
from dataclasses import dataclass


@dataclass
class Node:
    data: float
    left: Node | None = None
    right: Node | None = None

    def __iter__(self) -> Iterator[float]:
        
        if self.left:
            yield from self.left
        yield self.data
        if self.right:
            yield from self.right

    @property
    def is_sorted(self) -> bool:
        
        if self.left and (self.data < self.left.data or not self.left.is_sorted):
            return False
        if self.right and (self.data > self.right.data or not self.right.is_sorted):
            return False
        return True


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    tree = Node(data=2.1, left=Node(data=2.0), right=Node(data=2.2))
    print(f"Tree {list(tree)} is sorted: {tree.is_sorted = }.")
    assert tree.right
    tree.right.data = 2.0
    print(f"Tree {list(tree)} is sorted: {tree.is_sorted = }.")
    tree.right.data = 2.1
    print(f"Tree {list(tree)} is sorted: {tree.is_sorted = }.")