Frames

Untitled

0
1#include <algorithm>
2#include <iostream>
3#include <vector>
4#include <tuple>
5
6using std::vector;
7
8template <typename TINT>
9struct Node {
10 TINT key;
11 int left;
12 int right;
13
14 Node() : key(0), left(-1), right(-1) {}
15 Node(TINT key_, int left_, int right_) : key(key_), left(left_), right(right_) {}
16};
17
18template <typename TINT>
19bool IsNodeOk(const vector<Node<TINT>>& tree, int current, std::tuple<TINT,TINT> boundary){
20 auto l = tree[current].left;
21 auto r = tree[current].right;
22 auto currentValue = tree[current].key;
23
24 // std::cout << current << " " << currentValue << " " << std::get<0>(boundary) << " " << std::get<1>(boundary) << std::endl;
25
26 if(currentValue < std::get<0>(boundary)) return false;
27 if(currentValue >= std::get<1>(boundary)) return false;
28
29 if(l >= 0)
30 {
31 auto ok = IsNodeOk(tree, l, std::make_tuple(std::get<0>(boundary),currentValue));
32 if(ok == false) return false;
33 }
34
35 if(r >= 0)
36 {
37 auto ok = IsNodeOk(tree, r, std::make_tuple(currentValue,std::get<1>(boundary)));
38 if(ok == false) return false;
39 }
40
41 return true;
42}
43
44template <typename TINT>
45bool IsBinarySearchTree(const vector<Node<TINT>>& tree) {
46 if(tree.size() == 0) return true;
47 return IsNodeOk(tree, 0, std::make_tuple(
48 std::numeric_limits<TINT>::min(),
49 std::numeric_limits<TINT>::max()
50 ));
51}
52
53template <typename TINT>
54void run(std::istream& in, std::ostream& out)
55{
56 int nodes;
57 in >> nodes;
58 vector<Node<TINT>> tree;
59 for (int i = 0; i < nodes; ++i) {
60 TINT key;
61 int left, right;
62 in >> key >> left >> right;
63 tree.push_back({key, left, right});
64 }
65 if (IsBinarySearchTree(tree)) {
66 out << "CORRECT" << std::endl;
67 } else {
68 out << "INCORRECT" << std::endl;
69 }
70}
71
72#ifdef UNITTESTS
73
74#define CATCH_CONFIG_MAIN
75#include "../../catch.hpp"
76
77void test(const std::string& instr, const std::string& expectedOutStr)
78{
79 auto instream = std::stringstream{instr};
80 auto expectedstream = std::stringstream{expectedOutStr};
81
82 auto outstream = std::stringstream{};
83
84 run<long long>(instream, outstream);
85 outstream.seekg(0);
86
87 // std::cout << outstream.str() << std::endl;
88 // outstream.seekg(0);
89
90 std::string actual, expected;
91 while(!expectedstream.eof())
92 {
93 expectedstream >> expected;
94 outstream >> actual;
95
96 REQUIRE(expected == actual);
97 }
98}
99
100TEST_CASE("","")
101{
102 // test(R"(3
103 // 2 1 2
104 // 1 -1 -1
105 // 3 -1 -1)","CORRECT");
106 // test(R"(3
107 // 2 1 2
108 // 1 -1 -1
109 // 2 -1 -1)","CORRECT");
110 test(R"(1
111 2147483647 -1 -1)","CORRECT");
112}
113
114#else
115
116int main()
117{
118 run<long long>(std::cin, std::cout);
119 return 0;
120}
121
122#endif
123