Chương trình tìm phần tử nhỏ thứ K trong cây nhị phân tìm kiếm trong Python

Cho cây nhị phân tìm kiếm (BST) và số , tìm giá trị nhỏ thứ (1-indexed).

Ví dụ: cây như hình, → kết quả 7.

Giải thuật (Duyệt in-order lặp với Stack)

1. Khởi tạo , , .
2. Khi hoặc không rỗng:
   • Đi về trái nhất: .
   • Pop .
   • Nếu (0-indexed): , break.
   • , .
3. Trả về .

Ví dụ minh họa

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

class Solution:
    def solve(self, root, k):
        stack = []
        i = 0
        ans = -1
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            v = stack.pop()
            if i == k - 1:
                ans = v.val
                break
            root = v.right
            i += 1
        return ans

ob = Solution()
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.right.left = TreeNode(7)
root.right.right = TreeNode(15)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
print(ob.solve(root, 3))  # Output: 7

Đầu vào

root = TreeNode(5) root.left = TreeNode(4) root.right = TreeNode(10) root.right.left = TreeNode(7) root.right.right = TreeNode(15) root.right.left.left = TreeNode(6) root.right.left.right = TreeNode(8) 3

Đầu ra

7