หาค่าที่เป็นอันดับ k จากน้อยไปมากใน Binary Search Tree (BST)
คุณสมบัติ BST
Inorder traversal ให้ค่าจากน้อยไปมาก → ตัวที่ k ใน inorder คือคำตอบ
ตัวอย่าง
BST: 10
/ \
5 15
/ \ /
2 7 13
k=3 → 7
วิธีที่ 1: Inorder Traversal เก็บทั้งหมด (O(n) space)
class Solution:
def kthSmallest(self, root, k):
def inorder(node):
if not node:
return
inorder(node.left)
vals.append(node.val)
inorder(node.right)
vals = []
inorder(root)
return vals[k-1]
วิธีที่ 2: Iterative + Early Stop (O(h) space, h=height)
class Solution:
def kthSmallest(self, root, k):
stack = []
while True:
while root:
stack.append(root)
root = root.left
root = stack.pop()
k -= 1
if k == 0:
return root.val
root = root.right
สรุป
วิธี iterative ดีกว่า เพราะหยุดได้ทันทีที่เจอ ไม่ต้อง traverse ทั้งต้นไม้
