Binary Search Treeのvalidationコードをstackを利用するも微妙なエッジケースのカバーがなかなかできない。

Question

下記のコードで正常系BSTの確認をするコードは実装できましたが、[0,-1]のような片方しかないTree構造の場合のエッジケースがカバーできません。
そのエッジケースに特化したコードを実装しようとすると、こんごは正常系BSTのvalidateが通らなくなるコードができてしまいます。

下記Stackで実装されたコードをちょっとこう変えるだけでエッジケースのカバーができるなどお気づきの点ありましたらご教示いただけませんしょうか？

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST 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.

98. Validate Binary Search Tree

Stackで実装したBSTのvalidationコード

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return False

        if not root.left and not root.right:
            return True            
        
        stack = [[root, root.val]]
        left_val, right_val = -float("inf"), -float("inf")
        while stack:
            curr, val = stack.pop()
            
            if curr.left:
                stack.append([curr.left, curr.left.val])
                left_val = curr.left.val
            
            if curr.right:
                stack.append([curr.right, curr.right.val])
                right_val = curr.right.val
            
            if left_val < val < right_val:
                return True
            else:
                return False
        
        return True

成功する。

Your input [2,1,3]
Output true
Expected true

下記のインプットの場合のエッジケースをどうすればカバーできるか。

Input:　[0,-1]
Output:　false
Expected: true

Answer 1

提示されたコードを見ていると、以下のような勘違いをしているのではないかと心配になってしまいます。

すべてのノードについて、左の子ノードの値 < そのノードの値 < 右の子ノードの値 という条件が満たされれば、正常なBSTである。

念のため、反例を出しておきます。

リンク先の例2で、「4」と「5」を入れ替えた木を考えます。
入力としては、root = [4,1,5,null,null,3,6]となるでしょうか。

すべてのノードについて、上記の判断基準を満たすか確認してみます。

まず「4」のノードですが、左が「1」で右が「5」なので 1 < 4 < 5 で条件を満たします。
次に「5」のノードですが、左が「3」で右が「6」なので 3 < 5 < 6 で条件を満たします。
すべてのノードで条件を満たすので、この基準に従うなら、正常なBSTであると判定されます。

しかし、「4」の右のサブツリー内に「3」が存在するので、以下の条件が満たされていないことが分かります。

• The right subtree of a node contains only nodes with keys greater than the node's key.

つまり、この木は正常なBSTではありません。
よって、最初に示した判断基準では、正常なBSTの判定ができないということが分かります。

Answer 2

エッジケースでも何でもないです。
うまくいってるほうがたまたまです。

LeetCodeだと自分でテストケースを試せるのでいろいろ試してみてください。いくらでも間違った結果が出ます。