Algorithms : complete 02-data_structures 04-binary_search_trees

1 files changed, 34 insertions, 9 deletions

diff --git a/02-data_structures/04-binary_search_trees/01-tree_orders/tree-orders.cpp b/02-data_structures/04-binary_search_trees/01-tree_orders/tree-orders.cpp
index 5ee679c..d9437fa 100644
--- a/02-data_structures/04-binary_search_trees/01-tree_orders/tree-orders.cpp
+++ b/02-data_structures/04-binary_search_trees/01-tree_orders/tree-orders.cpp
@@ -27,27 +27,52 @@ public:
 
   vector <int> in_order() {
     vector<int> result;
-    // Finish the implementation
-    // You may need to add a new recursive method to do that
+    in_order_visit(0, result);
 
     return result;
   }
 
   vector <int> pre_order() {
-    vector<int> result;    
-    // Finish the implementation
-    // You may need to add a new recursive method to do that
-    
+    vector<int> result;
+    pre_order_visit(0, result);
+
     return result;
   }
 
   vector <int> post_order() {
     vector<int> result;
-    // Finish the implementation
-    // You may need to add a new recursive method to do that
-    
+    post_order_visit(0, result);
+
     return result;
   }
+private:
+
+  void in_order_visit(int n, vector<int> &r)
+  {
+      if (left[n] != -1)
+          in_order_visit(left[n], r);
+      r.push_back(key[n]);
+      if (right[n] != -1)
+          in_order_visit(right[n], r);
+  }
+
+  void pre_order_visit(int n, vector<int> &r)
+  {
+      r.push_back(key[n]);
+      if (left[n] != -1)
+          pre_order_visit(left[n], r);
+      if (right[n] != -1)
+          pre_order_visit(right[n], r);
+  }
+
+  void post_order_visit(int n, vector<int> &r)
+  {
+      if (left[n] != -1)
+          post_order_visit(left[n], r);
+      if (right[n] != -1)
+          post_order_visit(right[n], r);
+      r.push_back(key[n]);
+  }
 };
 
 void print(vector <int> a) {