Làm thế nào để xác định một cây nhị phân có phải là cây nhị phân tìm kiếm (BST) hợp lệ hay không? Những lỗi logic nào thường gặp khi lập trình viên Junior giải quyết bài toán này?

Question

Accepted Answer

Lỗi logic thường gặp
Nhiều lập trình viên Junior thường chỉ kiểm tra điều kiện: node.left.val < node.val < node.right.val. Cách này sai vì nó không kiểm tra được các nút ở nhánh con xa hơn. Ví dụ: một nút bên phải của gốc có thể nhỏ hơn gốc, vi phạm tính chất BST.
Giải pháp đúng
Sử dụng kỹ thuật truyền khoảng giá trị (Range Validation). Mỗi nút phải nằm trong một khoảng (min, max) xác định.
def is_valid_bst(node, min_val=float('-inf'), max_val=float('inf')):
    if not node: return True
    if not (min_val < node.val < max_val): return False
    return is_valid_bst(node.left, min_val, node.val) and \
           is_valid_bst(node.right, node.val, max_val)
Lưu ý thực chiến
Luôn sử dụng các kiểu dữ liệu có độ chính xác cao hoặc giá trị vô cực (Infinity) để thiết lập biên giới cho khoảng giá trị, đảm bảo không bỏ sót các trường hợp biên.

Làm thế nào để xác định một cây nhị phân có phải là cây nhị phân tìm kiếm (BST) hợp lệ hay không? Những lỗi logic nào thường gặp khi lập trình viên Junior giải quyết bài toán này?

Lỗi logic thường gặp

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi trees liên quan cùng chủ đề