data_structures.binary_tree.is_sorted

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.com/problems/validate-binary-search-tree/

If n is the number of nodes in the tree then: Runtime: O(n) Space: O(1)

Attributes

tree

Classes

Node

Module Contents

class data_structures.binary_tree.is_sorted.Node

__iter__() → collections.abc.Iterator[float]

>>> 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]

data: float

property is_sorted: bool

>>> 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'

left: Node | None = None

right: Node | None = None

data_structures.binary_tree.is_sorted.tree