(btree)+recursive insert algorithm

Just checks the value of the current node against value, assesses if
the leaf it needs to store it in is a NULL or not, then either
allocates to that leaf or recursively calls insert on that leaf (so it
may sort the value).  Uses pointer magic for some cleaner code.

1 files changed, 26 insertions, 0 deletions

diff --git a/btree.cpp b/btree.cpp
index c22c297..0ac794f 100644
--- a/btree.cpp
+++ b/btree.cpp
@@ -24,3 +24,29 @@ struct BinaryTree
   }
 };
 
+template <typename T>
+BinaryTree<T> *insert(BinaryTree<T> *tree, T value)
+{
+  BinaryTree<T> **node = &tree;
+  switch (tree->compare(value, tree->value))
+  {
+  case LT:
+    node = &tree->left;
+    break;
+  case EQ:
+  case GT:
+    node = &tree->right;
+    break;
+  }
+
+  if (*node) {
+    *node = insert(*node, value);
+    return tree;
+  }
+  *node = new BinaryTree<T>;
+  (*node)->value = value;
+  (*node)->left = (*node)->right = nullptr;
+  (*node)->compare = tree->compare;
+  return tree;
+}
+