// Created by Ketan Lalcheta /* //Trying to find out whether tree is BST or not //Input is N as number of nodes //Later on lines (N-1) shows edges among nodes //Input 7 2 1 2 3 4 2 4 6 6 5 6 7 //output //BST */ #include #include #include #include using namespace std; enum TreeType {tBT, tBST}; struct Node { public: int data; bool HasLeft, HasRight; int Leftdata, Rightdata; static bool AddEdge(vector&, int ,int); bool operator==(const Node& obj) { cout << "Oper data==obj: " << this->data << " == " << obj.data; if(this->data == obj.data) { cout << " (true)" << endl; return true; } else { cout << " (false)" << endl; return false; } } }; using vIterator = vector::iterator; vIterator findNode(vIterator firstNode, vIterator lastNode, const Node& aNode) { while (firstNode != lastNode) { if (**firstNode == aNode) { return firstNode; } firstNode++; } return lastNode; } bool AddNewEntry(vector& input, int data,int newdata) { Node* curNode = new Node; curNode->data = data; if(data>newdata) { curNode->HasLeft = true; curNode->HasRight = false; curNode->Leftdata = newdata; cout << "Add left edge" << endl; } else if(dataHasRight = true; curNode->HasLeft = false; curNode->Rightdata = newdata; cout << "Add right edge" << endl; } else { cout << "Edge matched!" << endl; return false; } input.push_back(curNode); return true; } bool Node::AddEdge(vector& input, int data,int newdata) { if(input.empty()) { cout << "Inside empty for " << data << " " << newdata << endl; return AddNewEntry(input,data,newdata); } else { Node* curNode = new Node; curNode->data = data; auto itr = findNode(input.begin(), input.end(), *curNode); if(itr==input.end()) { cout << "Inside new entry for " << data << " " << newdata << endl; return AddNewEntry(input,data,newdata); } else { cout << "Inside existing entry for " << data << " " << newdata << endl; if (data > newdata && !((*itr)->HasLeft)) { (*itr)->HasLeft = true; (*itr)->Leftdata = newdata; cout << "Left edge linked" << endl; } else if (data < newdata && !((*itr)->HasRight)) { (*itr)->HasRight = true; (*itr)->Rightdata = newdata; cout << "Right edge linked" << endl; } else { cout << "Node mismatch!" << endl; return false; } } } return true; } int main() { int n, data, newdata; TreeType tType = tBST; vector input; cin >> n; for (int i = 1; i < n; i++) { cin >> data >> newdata; cout << "Processing row: " << data << " " << newdata << endl; if (!Node::AddEdge(input, data, newdata)) { tType = tBT; } } cout << "Tree type is: " << (tType == tBST ? "BST" : "BT"); }

BST (Ketan Lalcheta)