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

Không có ý kiến tại thời điểm này.