LeetCode 98: ตรวจ BST ด้วย Bound หรือ Inorder แบบไหนชัดกว่า

โจทย์ Validate Binary Search Tree ให้รากของ binary tree แล้วถามว่าทั้งต้นเป็น BST ถูกต้องหรือไม่ ทุกค่าฝั่งซ้ายต้องน้อยกว่า node และทุกค่าฝั่งขวาต้องมากกว่า โดยเงื่อนไขครอบคลุมทั้ง subtree ไม่ใช่แค่ลูกติดกัน

WHY: เทียบกับ Parent อย่างเดียวไม่พอ

ต้นที่ root เป็น 10, ลูกซ้ายเป็น 5 แต่หลานขวาของ 5 เป็น 12 ผ่านการเทียบ 12 > 5 ทว่า 12 อยู่ใน subtree ซ้ายของ 10 จึงผิดครับ เราต้องส่งขอบเขตจากบรรพบุรุษลงไป หรือใช้คุณสมบัติว่า inorder traversal ของ BST ต้องเพิ่มขึ้นแบบ strict

วิธี 1: Recursive Bounds

ส่ง lower และ upper bound ให้แต่ละ node ฝั่งซ้ายรับ upper เป็นค่าปัจจุบัน ฝั่งขวารับ lower เป็นค่าปัจจุบัน เวลา O(n), call stack O(h) โดย h คือความสูง อ่านตรงกับนิยามและเป็น best default แต่ต้นเอียงลึกมากอาจชน recursion limit

วิธี 2: Iterative Inorder

ใช้ stack เดิน left-root-right แล้วตรวจว่าค่าปัจจุบันมากกว่า previous แบบ strict เวลา O(n), พื้นที่ O(h) ไม่เสี่ยง recursion depth และเหมาะกับต้นลึก ข้อเสียคือ invariant ของ traversal อ้อมกว่านิยาม bounds เล็กน้อย

วิธี 3: Collect แล้วตรวจ

เก็บ inorder ทั้งหมดใน list แล้วตรวจทุกคู่ เวลา O(n), พื้นที่ O(n) อ่านและ debug ง่าย เหมาะกับ input เล็กหรือเมื่อ list จะถูกใช้ต่อ แต่เก็บข้อมูลเกินจำเป็นและตรวจผิดช้ากว่า

import unittest
from dataclasses import dataclass


@dataclass
class Node:
    value: int
    left: "Node | None" = None
    right: "Node | None" = None


def valid_with_bounds(root):
    def visit(node, lower, upper):
        if node is None:
            return True
        if lower is not None and node.value <= lower:
            return False
        if upper is not None and node.value >= upper:
            return False
        return (
            visit(node.left, lower, node.value)
            and visit(node.right, node.value, upper)
        )
    return visit(root, None, None)


def valid_with_iterative_inorder(root):
    stack, current, previous = [], root, None
    while stack or current is not None:
        while current is not None:
            stack.append(current)
            current = current.left
        current = stack.pop()
        if previous is not None and current.value <= previous:
            return False
        previous = current.value
        current = current.right
    return True


def valid_with_collected_inorder(root):
    values = []
    def collect(node):
        if node is None:
            return
        collect(node.left)
        values.append(node.value)
        collect(node.right)
    collect(root)
    return all(left < right for left, right in zip(values, values[1:]))


class ValidateBSTTests(unittest.TestCase):
    def test_all_methods(self):
        valid = Node(2, Node(1), Node(3))
        cross_boundary = Node(10, Node(5, None, Node(12)), Node(15))
        duplicate = Node(2, Node(2), None)
        for method in (
            valid_with_bounds,
            valid_with_iterative_inorder,
            valid_with_collected_inorder,
        ):
            self.assertTrue(method(valid))
            self.assertTrue(method(None))
            self.assertFalse(method(cross_boundary))
            self.assertFalse(method(duplicate))


if __name__ == "__main__":
    unittest.main()

Decision Table

สภาพ input	Recursive bounds	Iterative inorder	Collect inorder
ต้นขนาดทั่วไป	ดีที่สุด	ดี	ใช้ได้
ต้นเอียงลึกมาก	เสี่ยง call stack	ดีที่สุด	ยังเสี่ยงถ้า collect แบบ recursive
memory จำกัด	O(h)	O(h)	O(n)
readability ตามนิยาม	ชัดที่สุด	ปานกลาง	ชัดตอนตรวจ list
streaming traversal	หยุดเร็วได้	เหมาะและหยุดเร็ว	ต้องเก็บครบ
input sorted/ไม่ sorted	ใช้โครงสร้าง tree	ใช้ inorder order	ใช้ inorder order
ห้ามแก้ input	ผ่าน	ผ่าน	ผ่าน

Edge Cases และ Trade-offs

ต้นว่างถือว่าถูกต้อง ค่า duplicate ต้องผิดเพราะ inequalities เป็น strict อย่าใช้ค่าต่ำสุด/สูงสุดของ integer เป็น sentinel ในภาษา fixed-width เพราะ node อาจมีค่าเท่านั้นพอดี ใช้ nullable bound หรือชนิดที่กว้างกว่า

recursive bounds เป็น best default เพราะแสดงกติกาของ subtree โดยตรงและหยุดเมื่อพบจุดผิด หาก constraints อนุญาตต้นลึกถึงหลักแสน ให้เปลี่ยนเป็น iterative inorder หรือ iterative stack ที่พก bounds

Recap

• กติกา BST มาจากบรรพบุรุษทั้งหมด
• duplicate ไม่ผ่าน strict ordering
• recursive bounds ตรงนิยามและใช้ O(h)
• iterative inorder เหมาะกับต้นลึก
• ไม่ต้อง mutate tree ในทุกวิธี