Двоичное дерево поиска Python: проверьте, является ли двоичное дерево действительным или нет

Дерево бинарного поиска Python: упражнение-3 с решением

Напишите программу на Python, чтобы проверить, является ли данное двоичное дерево действительным двоичным деревом поиска (BST) или нет.

Пусть двоичное дерево поиска (BST) определяется следующим образом:
Левое поддерево узла содержит только узлы с ключами, меньшими, чем ключ узла.
Правое поддерево узла содержит только узлы с ключами, которые больше ключа узла.
Левое и правое поддеревья также должны быть деревьями двоичного поиска.

 Пример 1:
    2
   / /
  1 3
Двоичное дерево [2,1,3], верните true.
Пример 2:
    1
   / /
  2 3
Двоичное дерево [1,2,3], вернуть false.

Пример решения :

Код Python:

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
def is_BST(root):
    stack = []
    prev = None
    
    while root or stack:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        if prev and root.val <= prev.val:
            return False
        prev = root
        root = root.right
    return True
root = TreeNode(2)  
root.left = TreeNode(1)  
root.right = TreeNode(3) 
 
result = is_BST(root)
print(result)
root = TreeNode(1)  
root.left = TreeNode(2)  
root.right = TreeNode(3) 
 
result = is_BST(root)
print(result)

Пример вывода:

 Правда
Ложь

Блок - схема:

Редактор кода Python:

Внесите свой код и комментарии через Disqus.

Предыдущий: Напишите программу на Python, чтобы найти ближайшее значение заданного целевого значения в заданном непустом двоичном дереве поиска (BST) с уникальными значениями.
Далее: Напишите программу на Python для удаления узла с данным ключом в заданном дереве двоичного поиска (BST).