From 36d6a0c2b7c63d52f50e1509deed1f96ff1435d0 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Wed, 12 Jun 2019 11:33:33 -0500
Subject: Binary Serach Tree check done!

I was lazy and didn't write test cases for this, because it's more or
less a straight copy from Java code, with minor modifications. In the
process I forgot to check 0 sized vector, and got "unknown signal 11"
segmentation fault error. Easy fix :)---
 Sources/DataStructure.cpp | 126 ++++++++--------------------------------------
 1 file changed, 20 insertions(+), 106 deletions(-)

(limited to 'Sources')

diff --git a/Sources/DataStructure.cpp b/Sources/DataStructure.cpp
index 4c0379b..ebb4c2e 100644
--- a/Sources/DataStructure.cpp
+++ b/Sources/DataStructure.cpp
@@ -2,17 +2,13 @@
 #include <vector>
 #include <algorithm>
 #include <stack>
-#include <queue>
-#include <unordered_set>
 //#include <gtest/gtest.h>
-//#if defined(__unix__) || defined(__APPLE__)
-//#include <sys/resource.h>
-//#endif
 
 using std::vector;
 using std::ios_base;
 using std::cin;
 using std::cout;
+using std::endl;
 
 class TreeOrders {
 public:
@@ -31,7 +27,8 @@ public:
 		}
 	}
 
-	vector<int> in_order() {
+	bool is_Bst() {
+		if (key.size()==0) return true;
 		std::stack<int> keyIndexStack;
 		vector<int> result;
 		bool walkLeft = true;
@@ -40,15 +37,21 @@ public:
 		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 {
-					result.push_back(key[keyIndexStack.top()]);
-					keyIndexStack.pop();
-					walkLeft = false;
+                    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;
@@ -56,107 +59,17 @@ public:
 					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 result;
+		return true;
 	}
 
-	vector<int> pre_order() {
-		vector<int> result;
-		std::stack<int> keyIndexStack;
-		std::queue<int> keyIndexQueue;
-		bool walkLeft = true;
-		int currentIndex = 0;
-		keyIndexStack.push(currentIndex);
-		keyIndexQueue.push(currentIndex);
-		while (!keyIndexStack.empty() || right[currentIndex] != -1) {
-			if (walkLeft) {
-				if (left[currentIndex] != -1) {
-					currentIndex = left[currentIndex];
-					keyIndexQueue.push(currentIndex);
-					keyIndexStack.push(currentIndex);
-				} else {
-					keyIndexStack.pop();
-					walkLeft = false;
-					result.push_back(key[keyIndexQueue.front()]);
-					keyIndexQueue.pop();
-				}
-			} else {
-				if (right[currentIndex] != -1) {
-					currentIndex = right[currentIndex];
-					keyIndexQueue.push(currentIndex);
-					keyIndexStack.push(currentIndex);
-					walkLeft = true;
-				} else {
-					if (!keyIndexStack.empty()) {
-						currentIndex = keyIndexStack.top();
-						keyIndexStack.pop();
-						result.push_back(key[keyIndexQueue.front()]);
-						keyIndexQueue.pop();
-					}
-				}
-			}
-		}
-		return result;
-	}
-
-	vector<int> post_order() {
-		vector<int> result;
-		std::stack<int> keyIndexStack;
-		std::unordered_set<int> peekedSet;
-		bool walkLeft = true;
-		int currentIndex = 0;
-		keyIndexStack.push(currentIndex);
-		while (!keyIndexStack.empty()) {
-			auto search = peekedSet.find(currentIndex);
-			if (search != peekedSet.end()) {
-				result.push_back(key[currentIndex]);
-				peekedSet.erase(currentIndex);
-				keyIndexStack.pop();
-				if (keyIndexStack.empty())
-					break;
-				currentIndex = keyIndexStack.top();
-				continue;
-			}
-			if (walkLeft) {
-				if (left[currentIndex] != -1) {
-					currentIndex = left[currentIndex];
-					keyIndexStack.push(currentIndex);
-				} else {
-					if (right[currentIndex] == -1) {
-						result.push_back(key[currentIndex]);
-						walkLeft = false;
-						keyIndexStack.pop();
-						currentIndex = keyIndexStack.top();
-					} else {
-						peekedSet.insert(currentIndex);
-						currentIndex = right[currentIndex];
-						keyIndexStack.push(currentIndex);
-					}
-				}
-			} else {
-				if (right[currentIndex] != -1) {
-					peekedSet.insert(currentIndex);
-					currentIndex = right[currentIndex];
-					keyIndexStack.push(currentIndex);
-					walkLeft = true;
-				} else {
-					result.push_back(key[currentIndex]);
-					int i = keyIndexStack.top();
-					keyIndexStack.pop();
-					if (i != currentIndex)
-						result.push_back(key[i]);
-					if (keyIndexStack.empty())
-						break;
-					currentIndex = keyIndexStack.top();
-				}
-			}
-		}
-		return result;
-	}
 };
 
 void print(vector<int> a) {
@@ -204,9 +117,10 @@ int main_with_large_stack_space() {
 	ios_base::sync_with_stdio(0);
 	TreeOrders t;
 	t.read();
-	print(t.in_order());
-	print(t.pre_order());
-	print(t.post_order());
+	if (t.is_Bst())
+		cout << "CORRECT" << endl;
+	else
+		cout << "INCORRECT" << endl;
 	return 0;
 }
 
-- 
cgit v1.2.3