From 55a24fc5601e05c7dfad9149bc93ac44302f94ae Mon Sep 17 00:00:00 2001
From: Aryadev Chavali <aryadev@aryadevchavali.com>
Date: Tue, 23 Nov 2021 06:19:13 +0000
Subject: (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.
---
 btree.cpp | 26 ++++++++++++++++++++++++++
 1 file changed, 26 insertions(+)

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;
+}
+
-- 
cgit v1.2.3-13-gbd6f