Tìm kiếm trong BST
Xem dưới dạng PDF
Gửi bài giải
Điểm:
20
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
đầu vào:
stdin
Đầu ra:
stdout
Tác giả:
Kiểu bài tập
Tèo có một dãy số nguyên dương phân biệt. Cậu ấy xây dựng một cây tìm kiếm nhị phân (BST) bằng cách lần lượt chèn từng số trong dãy vào cây. Sau đó, Tèo muốn kiểm tra xem một giá trị \(x\) có tồn tại trong cây hay không.
Hãy giúp Tèo viết chương trình kiểm tra sự tồn tại của giá trị \(x\) trong BST.
Định dạng đầu vào
- Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 10^3\)).
- Dòng thứ hai chứa \(N\) số nguyên dương phân biệt \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^9\)).
- \(Q\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(x\) (\(1 \le x \le 10^9\)).
Định dạng đầu ra
- Với mỗi giá trị \(x\), in ra \(YES\) nếu \(x\) tồn tại trong BST, ngược lại in ra \(NO\).
Ví dụ
Input:
7 3
5 3 7 2 4 6 8
4
9
2
Output:
YES
NO
YES
Giải thích: Cây BST được tạo từ dãy \([5, 3, 7, 2, 4, 6, 8]\). Giá trị \(4\) và \(2\) có tồn tại, giá trị \(9\) không tồn tại.
Nhận xét