LeetCode #230 Kth Smallest in BST: หยุด inorder เมื่อถึงลำดับ

Kth Smallest Element in a BST ให้รากของ binary search tree และ k ที่ถูกต้อง แล้วคืนค่าลำดับที่ k จากน้อยไปมาก คุณสมบัติสำคัญคือ inorder traversal ของ BST ให้ค่าที่เรียงแล้ว เราจึงไม่ต้องเอาทุกค่ามา sort ซ้ำครับ

วิธีที่ 1: Recursive inorder เก็บ list

เดินซ้าย-node-ขวา เก็บทุกค่าแล้วหยิบ index k-1 เวลา O(n), พื้นที่ O(n+h) อ่านง่ายที่สุดและเหมาะเมื่อจะใช้ลำดับทั้งหมดอยู่แล้ว แต่เสียงานถ้า k เล็ก

วิธีที่ 2: Iterative inorder หยุดเร็ว — ค่าเริ่มต้นที่แนะนำ

ใช้ stack เดินลงซ้ายสุด pop ทีละ node แล้วลด k เมื่อ k เป็นศูนย์คืนทันที เวลา O(h+k) โดยเฉลี่ยและ O(n) worst case; พื้นที่ O(h) ไม่พึ่ง recursion limit เหมาะกับโจทย์ครั้งเดียว

วิธีที่ 3: Augment subtree size

ถ้า node เก็บจำนวนสมาชิก subtree ซ้าย เราตัดสินได้ว่าจะลงซ้าย คืน node หรือไปขวาใน O(h) ต่อ query แต่ insert/delete ต้องอัปเดต size ให้ถูก เพิ่ม memory O(n) และ complexity ของระบบ เหมาะเมื่อ tree เปลี่ยนบ้างแต่ถาม kth หลายครั้ง

เงื่อนไข	เลือก	เหตุผล
query เดียว	Iterative early-stop	ไม่เก็บทั้ง tree
ต้องใช้ sorted values ต่อ	Full inorder list	ใช้ผลซ้ำได้
query จำนวนมาก	Subtree size	O(h) ต่อครั้ง
tree ลึกมาก	Iterative	เลี่ยง recursion limit
memory จำกัด	Morris traversal	O(1) แต่แก้ pointer ชั่วคราวและซับซ้อน
input เป็น stream	ใช้ไม่ได้ตรง ๆ	ต้องมีโครง tree หรือ sorted iterator
input เรียงแล้ว	หยิบ k ได้ตรง	ไม่ต้องสร้าง BST
ห้ามแก้ input	Iterative stack	ไม่แตะ pointer

import unittest


class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


def kth_smallest(root, k):
    stack = []
    current = root
    while current is not None or stack:
        while current is not None:
            stack.append(current)
            current = current.left
        current = stack.pop()
        k -= 1
        if k == 0:
            return current.value
        current = current.right
    raise ValueError("k is larger than the tree")


class KthSmallestTests(unittest.TestCase):
    def setUp(self):
        self.root = Node(5, Node(3, Node(2, Node(1)), Node(4)), Node(6))

    def test_first(self):
        self.assertEqual(kth_smallest(self.root, 1), 1)

    def test_middle(self):
        self.assertEqual(kth_smallest(self.root, 3), 3)

    def test_last(self):
        self.assertEqual(kth_smallest(self.root, 6), 6)

    def test_invalid_k(self):
        with self.assertRaises(ValueError):
            kth_smallest(self.root, 7)


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

Edge cases และ trade-off

แม้โจทย์รับประกัน k ถูกต้อง โค้ด reusable ควรตอบสนอง tree ว่างหรือ k เกินขนาดอย่างชัดเจน Tree เอียงทำให้ h เท่ากับ n และ stack ใหญ่ขึ้น ถ้าค่าซ้ำได้รับอนุญาตนอก constraints ต้องกำหนดว่าจะนับ node หรือค่าที่ไม่ซ้ำ

Recap

• ใช้ inorder เพราะ BST ให้ลำดับจากน้อยไปมาก
• ลด k ตอน visit node ไม่ใช่ตอน push
• หยุดทันทีเมื่อถึงลำดับ
• เพิ่ม subtree size เฉพาะระบบที่ query ซ้ำคุ้มต้นทุนดูแล
• ค่าเริ่มต้นภายใต้ constraints ของโจทย์: iterative inorder