#include #include #include #include //#include using std::vector; using std::ios_base; using std::cin; using std::cout; using std::endl; class TreeOrders { public: int n; vector key; vector left; vector right; void read() { cin >> n; key.resize(n); left.resize(n); right.resize(n); for (int i = 0; i < n; i++) { cin >> key[i] >> left[i] >> right[i]; } } bool is_Bst() { if (key.size()==0) return true; std::stack keyIndexStack; vector result; bool walkLeft = true; int currentIndex = 0; keyIndexStack.push(currentIndex); while (!keyIndexStack.empty() || right[currentIndex] != -1) { if (walkLeft) { if (left[currentIndex] != -1) { if (key[left[currentIndex]] >= key[currentIndex]) return false; currentIndex = left[currentIndex]; keyIndexStack.push(currentIndex); } else { int i = keyIndexStack.top(); keyIndexStack.pop(); if (result.size() > 0) { if (key[i] < result[(result.size()-1)]) return false; } result.push_back(key[i]); walkLeft = false; } } else { if (right[currentIndex] != -1) { if (key[right[currentIndex]] < key[currentIndex]) return false; currentIndex = right[currentIndex]; keyIndexStack.push(currentIndex); walkLeft = true; } else { if (!keyIndexStack.empty()) { currentIndex = keyIndexStack.top(); keyIndexStack.pop(); if (result.size() > 0) { if (key[currentIndex] <= result[(result.size()-1)]) return false; } result.push_back(key[currentIndex]); } } } } return true; } }; void print(vector a) { for (size_t i = 0; i < a.size(); i++) { if (i > 0) { cout << ' '; } cout << a[i]; } cout << '\n'; } //TEST(TreeTraversal, t) { // TreeOrders t; // t.key = {4, 2, 5, 1, 3}; // t.left = {1, 3, -1, -1, -1}; // t.right = {2, 4, -1, -1, -1}; // // vector results = t.in_order(); // ASSERT_EQ(5, results.size()); // ASSERT_EQ(1, results[0]); // ASSERT_EQ(2, results[1]); // ASSERT_EQ(3, results[2]); // ASSERT_EQ(4, results[3]); // ASSERT_EQ(5, results[4]); // // results = t.pre_order(); // ASSERT_EQ(5, results.size()); // ASSERT_EQ(4, results[0]); // ASSERT_EQ(2, results[1]); // ASSERT_EQ(1, results[2]); // ASSERT_EQ(3, results[3]); // ASSERT_EQ(5, results[4]); // // results = t.post_order(); // ASSERT_EQ(5, results.size()); // ASSERT_EQ(1, results[0]); // ASSERT_EQ(3, results[1]); // ASSERT_EQ(2, results[2]); // ASSERT_EQ(5, results[3]); // ASSERT_EQ(4, results[4]); //} int main_with_large_stack_space() { ios_base::sync_with_stdio(0); TreeOrders t; t.read(); if (t.is_Bst()) cout << "CORRECT" << endl; else cout << "INCORRECT" << endl; return 0; } int main (int argc, char **argv) { return main_with_large_stack_space(); }