Repository: codezonediitj/pydatastructs (language: python)

Issue:
Add C++ backend for all the trees present in `binary_trees.py`
#### Description of the problem
<!--Please provide a clear and details information of the bug/data structure to be added.-->

https://github.com/codezonediitj/pydatastructs/blob/main/pydatastructs/trees/binary_trees.py

Follow the pattern of C++ backend in `linear_data_structures` module.

Check https://github.com/codezonediitj/pydatastructs/tree/main/pydatastructs/linear_data_structures/_backend/cpp

#### Example of the problem
<!--Provide a reproducible example code which is causing the bug to appear. Leave this section if the problem is not a bug.-->

#### References/Other comments



Discussion / hints:
@Kishan-Ved Go ahead and take this up.
Sure, I'll start working on this. Thank you!
I've spent the day reading and understanding backend implementation of search algorithms. However, I'm finding it difficult to understand how to start the implementation from scratch, which files to include and which already defined utils to use. 
Can you please commit some starting code, which has files created with necessary imports and the BinaryTree class' backend implemented in c++. (it is a small code defined in binary_trees.py). Also please let me know if nodes are already defined in c++ backend.
This will help me understand and reuse the code to implement other classes.
I won’t be able to do that. Try checking how OneDimensionalArray is implemented. Follow the same pattern here.
Please check this once: #551

Fix patch:
diff --git a/pydatastructs/__init__.py b/pydatastructs/__init__.py
index 197fce03d..27cc5a202 100644
--- a/pydatastructs/__init__.py
+++ b/pydatastructs/__init__.py
@@ -1,7 +1,7 @@
+from .utils import *
 from .linear_data_structures import *
 from .trees import *
 from .miscellaneous_data_structures import *
-from .utils import *
 from .graphs import *
 from .strings import *
 
diff --git a/pydatastructs/linear_data_structures/__init__.py b/pydatastructs/linear_data_structures/__init__.py
index 5cbf47732..057adc169 100644
--- a/pydatastructs/linear_data_structures/__init__.py
+++ b/pydatastructs/linear_data_structures/__init__.py
@@ -10,7 +10,8 @@
 from .arrays import (
     OneDimensionalArray,
     DynamicOneDimensionalArray,
-    MultiDimensionalArray
+    MultiDimensionalArray,
+    ArrayForTrees
 )
 __all__.extend(arrays.__all__)
 
diff --git a/pydatastructs/linear_data_structures/_backend/cpp/algorithms/misc_algorithms.hpp b/pydatastructs/linear_data_structures/_backend/cpp/algorithms/misc_algorithms.hpp
index 8ced4a19a..452795568 100644
--- a/pydatastructs/linear_data_structures/_backend/cpp/algorithms/misc_algorithms.hpp
+++ b/pydatastructs/linear_data_structures/_backend/cpp/algorithms/misc_algorithms.hpp
@@ -16,7 +16,7 @@ static bool is_ordered_impl(PyObject* array, size_t lower, size_t upper,
         PyObject* i_item = PyObject_GetItem(array, i_PyObject);
         PyObject* i1_item = PyObject_GetItem(array, i1_PyObject);
         if (i_item == Py_None || i1_item == Py_None) continue;
-        if( _comp(i_item, i1_item, comp) == 1 ) {
+        if ( _comp(i_item, i1_item, comp) == 1 ) {
             return false;
         }
     }
@@ -30,23 +30,23 @@ static PyObject* is_ordered(PyObject* self, PyObject* args, PyObject* kwds) {
     args0 = PyObject_GetItem(args, PyZero);
     int is_DynamicOneDimensionalArray = _check_type(args0, &DynamicOneDimensionalArrayType);
     int is_OneDimensionalArray = _check_type(args0, &OneDimensionalArrayType);
-    if( !is_DynamicOneDimensionalArray && !is_OneDimensionalArray ) {
+    if ( !is_DynamicOneDimensionalArray && !is_OneDimensionalArray ) {
         raise_exception_if_not_array(args0);
         return NULL;
     }
     comp = PyObject_GetItem(kwds, PyUnicode_FromString("comp"));
-    if( comp == NULL ) {
+    if ( comp == NULL ) {
         PyErr_Clear();
     }
     start = PyObject_GetItem(kwds, PyUnicode_FromString("start"));
-    if( start == NULL ) {
+    if ( start == NULL ) {
         PyErr_Clear();
         lower = 0;
     } else {
         lower = PyLong_AsSize_t(start);
     }
     end = PyObject_GetItem(kwds, PyUnicode_FromString("end"));
-    if( end == NULL ) {
+    if ( end == NULL ) {
         PyErr_Clear();
         upper = PyObject_Length(args0) - 1;
     } else {
@@ -66,26 +66,26 @@ static PyObject* linear_search(PyObject* self, PyObject* args, PyObject* kwds) {
     args0 = PyObject_GetItem(args, PyZero);
     int is_DynamicOneDimensionalArray = _check_type(args0, &DynamicOneDimensionalArrayType);
     int is_OneDimensionalArray = _check_type(args0, &OneDimensionalArrayType);
-    if( !is_DynamicOneDimensionalArray && !is_OneDimensionalArray ) {
+    if ( !is_DynamicOneDimensionalArray && !is_OneDimensionalArray ) {
         raise_exception_if_not_array(args0);
         return NULL;
     }
     start = PyObject_GetItem(kwds, PyUnicode_FromString("start"));
-    if( start == NULL ) {
+    if ( start == NULL ) {
         PyErr_Clear();
         lower = 0;
     } else {
         lower = PyLong_AsSize_t(start);
     }
     end = PyObject_GetItem(kwds, PyUnicode_FromString("end"));
-    if( end == NULL ) {
+    if ( end == NULL ) {
         PyErr_Clear();
         upper = PyObject_Length(args0) - 1;
     } else {
         upper = PyLong_AsSize_t(end);
     }
     value = PyObject_GetItem(args, PyLong_FromSize_t(1));
-    if( value == NULL ) {
+    if ( value == NULL ) {
         PyErr_Format(PyExc_ValueError,
                 "Expected Value to be not NULL");
     }
@@ -120,30 +120,30 @@ static PyObject* binary_search(PyObject* self, PyObject* args, PyObject* kwds) {
     args0 = PyObject_GetItem(args, PyZero);
     int is_DynamicOneDimensionalArray = _check_type(args0, &DynamicOneDimensionalArrayType);
     int is_OneDimensionalArray = _check_type(args0, &OneDimensionalArrayType);
-    if( !is_DynamicOneDimensionalArray && !is_OneDimensionalArray ) {
+    if ( !is_DynamicOneDimensionalArray && !is_OneDimensionalArray ) {
         raise_exception_if_not_array(args0);
         return NULL;
     }
     comp = PyObject_GetItem(kwds, PyUnicode_FromString("comp"));
-    if( comp == NULL ) {
+    if ( comp == NULL ) {
         PyErr_Clear();
     }
     start = PyObject_GetItem(kwds, PyUnicode_FromString("start"));
-    if( start == NULL ) {
+    if ( start == NULL ) {
         PyErr_Clear();
         lower = 0;
     } else {
         lower = PyLong_AsSize_t(start);
     }
     end = PyObject_GetItem(kwds, PyUnicode_FromString("end"));
-    if( end == NULL ) {
+    if ( end == NULL ) {
         PyErr_Clear();
         upper = PyObject_Length(args0) - 1;
     } else {
         upper = PyLong_AsSize_t(end);
     }
     value = PyObject_GetItem(args, PyLong_FromSize_t(1));
-    if( value == NULL ) {
+    if ( value == NULL ) {
         PyErr_Format(PyExc_ValueError,
                 "Expected Value to be not NULL");
     }
@@ -169,7 +169,7 @@ static PyObject* binary_search(PyObject* self, PyObject* args, PyObject* kwds) {
             Py_INCREF(res);
             return res;
         }
-        if( _comp(u, value, comp) == 1 ) {
+        if ( _comp(u, value, comp) == 1 ) {
             left = middle + 1;
         } else {
             right = middle - 1;
@@ -187,30 +187,30 @@ static PyObject* jump_search(PyObject* self, PyObject* args, PyObject* kwds) {
     args0 = PyObject_GetItem(args, PyZero);
     int is_DynamicOneDimensionalArray = _check_type(args0, &DynamicOneDimensionalArrayType);
     int is_OneDimensionalArray = _check_type(args0, &OneDimensionalArrayType);
-    if( !is_DynamicOneDimensionalArray && !is_OneDimensionalArray ) {
+    if ( !is_DynamicOneDimensionalArray && !is_OneDimensionalArray ) {
         raise_exception_if_not_array(args0);
         return NULL;
     }
     comp = PyObject_GetItem(kwds, PyUnicode_FromString("comp"));
-    if( comp == NULL ) {
+    if ( comp == NULL ) {
         PyErr_Clear();
     }
     start = PyObject_GetItem(kwds, PyUnicode_FromString("start"));
-    if( start == NULL ) {
+    if ( start == NULL ) {
         PyErr_Clear();
         lower = 0;
     } else {
         lower = PyLong_AsSize_t(start);
     }
     end = PyObject_GetItem(kwds, PyUnicode_FromString("end"));
-    if( end == NULL ) {
+    if ( end == NULL ) {
         PyErr_Clear();
         upper = PyObject_Length(args0) - 1;
     } else {
         upper = PyLong_AsSize_t(end);
     }
     value = PyObject_GetItem(args, PyLong_FromSize_t(1));
-    if( value == NULL ) {
+    if ( value == NULL ) {
         PyErr_Format(PyExc_ValueError,
                 "Expected Value to be not NULL");
     }
diff --git a/pydatastructs/linear_data_structures/_backend/cpp/algorithms/quadratic_time_sort.hpp b/pydatastructs/linear_data_structures/_backend/cpp/algorithms/quadratic_time_sort.hpp
index 04e7fd119..45e2d6dee 100644
--- a/pydatastructs/linear_data_structures/_backend/cpp/algorithms/quadratic_time_sort.hpp
+++ b/pydatastructs/linear_data_structures/_backend/cpp/algorithms/quadratic_time_sort.hpp
@@ -14,7 +14,7 @@ static PyObject* bubble_sort_impl(PyObject* array, size_t lower, size_t upper,
         for (size_t j = lower; j < upper; j++) {
             PyObject* j_PyObject = PyLong_FromSize_t(j);
             PyObject* j1_PyObject = PyLong_FromSize_t(j+1);
-            if( _comp(PyObject_GetItem(array, j_PyObject),
+            if ( _comp(PyObject_GetItem(array, j_PyObject),
                         PyObject_GetItem(array, j1_PyObject), comp) != 1 ) {
                 PyObject* tmp = PyObject_GetItem(array, j1_PyObject);
                 PyObject_SetItem(array, j1_PyObject,
@@ -34,23 +34,23 @@ static PyObject* bubble_sort(PyObject* self, PyObject* args, PyObject* kwds) {
     args0 = PyObject_GetItem(args, PyZero);
     int is_DynamicOneDimensionalArray = _check_type(args0, &DynamicOneDimensionalArrayType);
     int is_OneDimensionalArray = _check_type(args0, &OneDimensionalArrayType);
-    if( !is_DynamicOneDimensionalArray && !is_OneDimensionalArray ) {
+    if ( !is_DynamicOneDimensionalArray && !is_OneDimensionalArray ) {
         raise_exception_if_not_array(args0);
         return NULL;
     }
     comp = PyObject_GetItem(kwds, PyUnicode_FromString("comp"));
-    if( comp == NULL ) {
+    if ( comp == NULL ) {
         PyErr_Clear();
     }
     start = PyObject_GetItem(kwds, PyUnicode_FromString("start"));
-    if( start == NULL ) {
+    if ( start == NULL ) {
         PyErr_Clear();
         lower = 0;
     } else {
         lower = PyLong_AsSize_t(start);
     }
     end = PyObject_GetItem(kwds, PyUnicode_FromString("end"));
-    if( end == NULL ) {
+    if ( end == NULL ) {
         PyErr_Clear();
         upper = PyObject_Length(args0) - 1;
     } else {
@@ -59,7 +59,7 @@ static PyObject* bubble_sort(PyObject* self, PyObject* args, PyObject* kwds) {
     arr_length = PyObject_Length(args0);
 
     args0 = bubble_sort_impl(args0, lower, upper, comp, arr_length);
-    if( is_DynamicOneDimensionalArray ) {
+    if ( is_DynamicOneDimensionalArray ) {
         PyObject_CallMethod(args0, "_modify", "O", Py_True);
     }
     Py_INCREF(args0);
@@ -75,7 +75,7 @@ static PyObject* selection_sort_impl(PyObject* array, size_t lower, size_t upper
         PyObject* i_PyObject = PyLong_FromSize_t(i);
         for (size_t j = i + 1; j < upper + 1; j++) {
             PyObject* j_PyObject = PyLong_FromSize_t(j);
-            if( _comp(PyObject_GetItem(array, j_min_PyObject),
+            if ( _comp(PyObject_GetItem(array, j_min_PyObject),
                         PyObject_GetItem(array, j_PyObject), comp) != 1 ) {
                 j_min_PyObject = j_PyObject;
             }
@@ -96,23 +96,23 @@ static PyObject* selection_sort(PyObject* self, PyObject* args, PyObject* kwds)
     args0 = PyObject_GetItem(args, PyZero);
     int is_DynamicOneDimensionalArray = _check_type(args0, &DynamicOneDimensionalArrayType);
     int is_OneDimensionalArray = _check_type(args0, &OneDimensionalArrayType);
-    if( !is_DynamicOneDimensionalArray && !is_OneDimensionalArray ) {
+    if ( !is_DynamicOneDimensionalArray && !is_OneDimensionalArray ) {
         raise_exception_if_not_array(args0);
         return NULL;
     }
     comp = PyObject_GetItem(kwds, PyUnicode_FromString("comp"));
-    if( comp == NULL ) {
+    if ( comp == NULL ) {
         PyErr_Clear();
     }
     start = PyObject_GetItem(kwds, PyUnicode_FromString("start"));
-    if( start == NULL ) {
+    if ( start == NULL ) {
         PyErr_Clear();
         lower = 0;
     } else {
         lower = PyLong_AsSize_t(start);
     }
     end = PyObject_GetItem(kwds, PyUnicode_FromString("end"));
-    if( end == NULL ) {
+    if ( end == NULL ) {
         PyErr_Clear();
         upper = PyObject_Length(args0) - 1;
     } else {
@@ -120,7 +120,7 @@ static PyObject* selection_sort(PyObject* self, PyObject* args, PyObject* kwds)
     }
 
     args0 = selection_sort_impl(args0, lower, upper, comp);
-    if( is_DynamicOneDimensionalArray ) {
+    if ( is_DynamicOneDimensionalArray ) {
         PyObject_CallMethod(args0, "_modify", "O", Py_True);
     }
     Py_INCREF(args0);
@@ -153,23 +153,23 @@ static PyObject* insertion_sort(PyObject* self, PyObject* args, PyObject* kwds)
     args0 = PyObject_GetItem(args, PyZero);
     int is_DynamicOneDimensionalArray = _check_type(args0, &DynamicOneDimensionalArrayType);
     int is_OneDimensionalArray = _check_type(args0, &OneDimensionalArrayType);
-    if( !is_DynamicOneDimensionalArray && !is_OneDimensionalArray ) {
+    if ( !is_DynamicOneDimensionalArray && !is_OneDimensionalArray ) {
         raise_exception_if_not_array(args0);
         return NULL;
     }
     comp = PyObject_GetItem(kwds, PyUnicode_FromString("comp"));
-    if( comp == NULL ) {
+    if ( comp == NULL ) {
         PyErr_Clear();
     }
     start = PyObject_GetItem(kwds, PyUnicode_FromString("start"));
-    if( start == NULL ) {
+    if ( start == NULL ) {
         PyErr_Clear();
         lower = 0;
     } else {
         lower = PyLong_AsSize_t(start);
     }
     end = PyObject_GetItem(kwds, PyUnicode_FromString("end"));
-    if( end == NULL ) {
+    if ( end == NULL ) {
         PyErr_Clear();
         upper = PyObject_Length(args0) - 1;
     } else {
@@ -177,7 +177,7 @@ static PyObject* insertion_sort(PyObject* self, PyObject* args, PyObject* kwds)
     }
 
     args0 = insertion_sort_impl(args0, lower, upper, comp);
-    if( is_DynamicOneDimensionalArray ) {
+    if ( is_DynamicOneDimensionalArray ) {
         PyObject_CallMethod(args0, "_modify", "O", Py_True);
     }
     Py_INCREF(args0);
diff --git a/pydatastructs/linear_data_structures/_backend/cpp/algorithms/quick_sort.hpp b/pydatastructs/linear_data_structures/_backend/cpp/algorithms/quick_sort.hpp
index 2227405fa..f3ad0ed07 100644
--- a/pydatastructs/linear_data_structures/_backend/cpp/algorithms/quick_sort.hpp
+++ b/pydatastructs/linear_data_structures/_backend/cpp/algorithms/quick_sort.hpp
@@ -11,7 +11,7 @@
 static PyObject* call_pick_pivot_element(PyObject* pick_pivot_element,
     size_t low, size_t high, PyObject* array) {
     PyObject* high_PyObject = PyLong_FromSize_t(high);
-    if( pick_pivot_element ) {
+    if ( pick_pivot_element ) {
         return PyObject_CallFunctionObjArgs(pick_pivot_element,
                                             PyLong_FromSize_t(low),
                                             high_PyObject,
@@ -27,7 +27,7 @@ static size_t quick_sort_partition(size_t low, size_t high,
     PyObject* x = call_pick_pivot_element(pick_pivot_element, low, high, array);
     for( size_t j = low; j < high; j++ ) {
         PyObject* j_PyObject = PyLong_FromSize_t(j);
-        if( _comp(PyObject_GetItem(array, j_PyObject), x, comp) == 1 ) {
+        if ( _comp(PyObject_GetItem(array, j_PyObject), x, comp) == 1 ) {
             i = i + 1;
             PyObject* i_PyObject = PyLong_FromLongLong(i);
             PyObject* tmp = PyObject_GetItem(array, i_PyObject);
@@ -54,18 +54,18 @@ static PyObject* quick_sort_impl(PyObject* array, size_t lower, size_t upper,
     rstack.push(lower);
     rstack.push(upper);
 
-    while( !rstack.empty() ) {
+    while ( !rstack.empty() ) {
         high = rstack.top();
         rstack.pop();
         low = rstack.top();
         rstack.pop();
         p = quick_sort_partition(low, high, pick_pivot_element,
                                  comp, array);
-        if( p - 1 > low ) {
+        if ( p - 1 > low ) {
             rstack.push(low);
             rstack.push(p - 1);
         }
-        if( p + 1 < high ) {
+        if ( p + 1 < high ) {
             rstack.push(p + 1);
             rstack.push(high);
         }
@@ -81,27 +81,27 @@ static PyObject* quick_sort(PyObject* self, PyObject* args, PyObject* kwds) {
     args0 = PyObject_GetItem(args, PyZero);
     int is_DynamicOneDimensionalArray = _check_type(args0, &DynamicOneDimensionalArrayType);
     int is_OneDimensionalArray = _check_type(args0, &OneDimensionalArrayType);
-    if( !is_DynamicOneDimensionalArray && !is_OneDimensionalArray ) {
+    if ( !is_DynamicOneDimensionalArray && !is_OneDimensionalArray ) {
         raise_exception_if_not_array(args0);
         return NULL;
     }
     comp = PyObject_GetItem(kwds, PyUnicode_FromString("comp"));
-    if( comp == NULL ) {
+    if ( comp == NULL ) {
         PyErr_Clear();
     }
     pick_pivot_element = PyObject_GetItem(kwds, PyUnicode_FromString("pick_pivot_element"));
-    if( pick_pivot_element == NULL ) {
+    if ( pick_pivot_element == NULL ) {
         PyErr_Clear();
     }
     start = PyObject_GetItem(kwds, PyUnicode_FromString("start"));
-    if( start == NULL ) {
+    if ( start == NULL ) {
         PyErr_Clear();
         lower = 0;
     } else {
         lower = PyLong_AsSize_t(start);
     }
     end = PyObject_GetItem(kwds, PyUnicode_FromString("end"));
-    if( end == NULL ) {
+    if ( end == NULL ) {
         PyErr_Clear();
         upper = PyObject_Length(args0) - 1;
     } else {
@@ -109,7 +109,7 @@ static PyObject* quick_sort(PyObject* self, PyObject* args, PyObject* kwds) {
     }
 
     args0 = quick_sort_impl(args0, lower, upper, comp, pick_pivot_element);
-    if( is_DynamicOneDimensionalArray ) {
+    if ( is_DynamicOneDimensionalArray ) {
         PyObject_CallMethod(args0, "_modify", "O", Py_True);
     }
     Py_INCREF(args0);
diff --git a/pydatastructs/linear_data_structures/_backend/cpp/arrays/Array.hpp b/pydatastructs/linear_data_structures/_backend/cpp/arrays/Array.hpp
index 65b59b349..a7e23ade6 100644
--- a/pydatastructs/linear_data_structures/_backend/cpp/arrays/Array.hpp
+++ b/pydatastructs/linear_data_structures/_backend/cpp/arrays/Array.hpp
@@ -22,7 +22,7 @@ static PyObject* Array___new__(PyTypeObject* type, PyObject *args,
 
 static PyObject* Array___str__(Array *self) {
     PyObject* self__data = PyObject_GetAttrString(reinterpret_cast<PyObject*>(self), "_data");
-    if( !self__data ) {
+    if ( !self__data ) {
         return NULL;
     }
     return PyObject_Str(self__data);
diff --git a/pydatastructs/linear_data_structures/_backend/cpp/arrays/ArrayForTrees.hpp b/pydatastructs/linear_data_structures/_backend/cpp/arrays/ArrayForTrees.hpp
new file mode 100644
index 000000000..4828fe7f8
--- /dev/null
+++ b/pydatastructs/linear_data_structures/_backend/cpp/arrays/ArrayForTrees.hpp
@@ -0,0 +1,260 @@
+#ifndef LINEAR_DATA_STRUCTURES_ARRAYFORTREES_HPP
+#define LINEAR_DATA_STRUCTURES_ARRAYFORTREES_HPP
+
+#define PY_SSIZE_T_CLEAN
+#include <Python.h>
+#include <structmember.h>
+#include <cstdlib>
+#include "OneDimensionalArray.hpp"
+#include "DynamicArray.hpp"
+#include "../../../../utils/_backend/cpp/TreeNode.hpp"
+#include "../../../../utils/_backend/cpp/utils.hpp"
+
+typedef struct {
+    PyObject_HEAD
+    OneDimensionalArray* _one_dimensional_array;
+    double _load_factor;
+    long _num;
+    long _last_pos_filled;
+    long _size;
+} ArrayForTrees;
+
+static void ArrayForTrees_dealloc(ArrayForTrees *self) {
+    OneDimensionalArray_dealloc(self->_one_dimensional_array);
+    Py_TYPE(self)->tp_free(reinterpret_cast<PyObject*>(self));
+}
+
+static PyObject* ArrayForTrees___new__(PyTypeObject* type, PyObject *args,
+                                                    PyObject *kwds) {
+    ArrayForTrees *self;
+    self = reinterpret_cast<ArrayForTrees*>(type->tp_alloc(type, 0));
+    if (PyType_Ready(&OneDimensionalArrayType) < 0) { // This has to be present to finalize a type object. This should be called on all type objects to finish their initialization.
+        return NULL;
+    }
+    PyObject* _one_dimensional_array = OneDimensionalArray___new__(&OneDimensionalArrayType, args, kwds);
+    if ( !_one_dimensional_array ) {
+        return NULL;
+    }
+    self->_one_dimensional_array = reinterpret_cast<OneDimensionalArray*>(_one_dimensional_array);
+    self->_size = (long) self->_one_dimensional_array->_size;
+
+    PyObject* _load_factor = PyObject_GetItem(kwds, PyUnicode_FromString("load_factor"));
+    if ( _load_factor == nullptr ) {
+        PyErr_Clear();
+        self->_load_factor = 0.25;
+    } else {
+        _load_factor = PyFloat_FromString(PyObject_Str(_load_factor));
+        if ( !_load_factor ) {
+            return NULL;
+        }
+        self->_load_factor = PyFloat_AS_DOUBLE(_load_factor);
+    }
+    if ( self->_one_dimensional_array->_size == 0 ||
+        self->_one_dimensional_array->_data[0] == Py_None ) {
+        self->_num = 0;
+    } else {
+        self->_num = (long) self->_one_dimensional_array->_size;
+    }
+    self->_last_pos_filled = (long) self->_num - 1;
+
+    return reinterpret_cast<PyObject*>(self);
+}
+
+static PyObject* ArrayForTrees___getitem__(ArrayForTrees *self,
+                                                        PyObject* arg) {
+    return OneDimensionalArray___getitem__(self->_one_dimensional_array, arg);
+}
+
+static int ArrayForTrees___setitem__(ArrayForTrees *self,
+                                                  PyObject* arg, PyObject* value) {
+    return OneDimensionalArray___setitem__(self->_one_dimensional_array, arg, value);
+}
+
+static PyObject* ArrayForTrees_fill(ArrayForTrees *self, PyObject *args) {
+    return OneDimensionalArray_fill(self->_one_dimensional_array, args);
+}
+
+static Py_ssize_t ArrayForTrees___len__(ArrayForTrees *self) {
+    return self->_one_dimensional_array->_size;
+}
+
+static PyObject* ArrayForTrees___str__(ArrayForTrees *self) {
+    PyObject** self__data = self->_one_dimensional_array->_data;
+    return __str__(self__data, self->_one_dimensional_array->_size, self->_last_pos_filled);
+}
+
+static PyObject* ArrayForTrees__modify(ArrayForTrees *self,
+                                                    PyObject* args) {
+
+    if (((double)self->_num/(double)self->_size) < self->_load_factor) {
+        PyObject* new_indices = PyDict_New();
+
+        long new_size = 2 * self->_num + 1;
+        PyObject** arr_new = reinterpret_cast<PyObject**>(std::malloc(new_size * sizeof(PyObject*)));
+        for( int i = 0; i < new_size; i++ ) {
+            Py_INCREF(Py_None);
+            arr_new[i] = Py_None;
+        }
+
+        int j=0;
+        PyObject** _data = self->_one_dimensional_array->_data;
+        for(int i=0; i<=self->_last_pos_filled;i++) {
+            if (_data[i] != Py_None) {
+                Py_INCREF(Py_None);
+                arr_new[j] = _data[i];
+                PyObject_SetItem(new_indices, reinterpret_cast<TreeNode*>(_data[i])->key, PyLong_FromLong(j));
+                j += 1;
+            }
+        }
+
+        for(int i=0;i<j;i++) {
+            if (reinterpret_cast<TreeNode*>(arr_new[i])->left != Py_None) {
+                reinterpret_cast<TreeNode*>(arr_new[i])->left = PyObject_GetItem(
+                    new_indices, reinterpret_cast<TreeNode*>(_data[PyLong_AsLong(reinterpret_cast<TreeNode*>(arr_new[i])->left)])->key
+                );
+            }
+            if (reinterpret_cast<TreeNode*>(arr_new[i])->right != Py_None) {
+                reinterpret_cast<TreeNode*>(arr_new[i])->right = PyObject_GetItem(
+                    new_indices, reinterpret_cast<TreeNode*>(_data[PyLong_AsLong(reinterpret_cast<TreeNode*>(arr_new[i])->right)])->key
+                );
+            }
+            if (reinterpret_cast<TreeNode*>(arr_new[i])->parent != Py_None) {
+                reinterpret_cast<TreeNode*>(arr_new[i])->parent = PyObject_GetItem(
+                    new_indices, reinterpret_cast<TreeNode*>(_data[PyLong_AsLong(reinterpret_cast<TreeNode*>(arr_new[i])->parent)])->key
+                );
+            }
+        }
+        self->_last_pos_filled = j - 1;
+        self->_one_dimensional_array->_data = arr_new;
+        self->_size = new_size;
+        self->_size = new_size;
+
+        return new_indices;
+    }
+    Py_RETURN_NONE;
+}
+
+static PyObject* ArrayForTrees_append(ArrayForTrees *self,
+                                                    PyObject* args) {
+    PyObject* el = PyObject_GetItem(args, PyZero);
+    if ( !el ) {
+        return NULL;
+    }
+
+    long _size = (long) self->_one_dimensional_array->_size;
+    PyObject** _data = self->_one_dimensional_array->_data;
+    if ( self->_last_pos_filled + 1 == _size ) {
+        long new_size = 2 * _size + 1;
+        PyObject** arr_new = reinterpret_cast<PyObject**>(std::malloc(new_size * sizeof(PyObject*)));
+        long i;
+        for( i = 0; i <= self->_last_pos_filled; i++ ) {
+            arr_new[i] = _data[i];
+        }
+        for( ; i < new_size; i++ ) {
+            arr_new[i] = Py_None;
+        }
+        arr_new[self->_last_pos_filled + 1] = el;
+        self->_one_dimensional_array->_size = new_size;
+        self->_size = new_size;
+        self->_one_dimensional_array->_data = arr_new;
+    } else {
+        _data[self->_last_pos_filled + 1] = el;
+    }
+    self->_last_pos_filled += 1;
+    self->_num += 1;
+    return ArrayForTrees__modify(self, NULL);
+}
+
+static PyObject* ArrayForTrees_delete(ArrayForTrees *self,
+                                                   PyObject* args) {
+    PyObject* idx_pyobject = PyObject_GetItem(args, PyZero);
+    if ( !idx_pyobject ) {
+        return NULL;
+    }
+    long idx = PyLong_AsLong(idx_pyobject);
+    if ( idx == -1 && PyErr_Occurred() ) {
+        return NULL;
+    }
+
+    PyObject** _data = self->_one_dimensional_array->_data;
+    if ( idx <= self->_last_pos_filled && idx >= 0 &&
+        _data[idx] != Py_None ) {
+        _data[idx] = Py_None;
+        self->_num -= 1;
+        if ( self->_last_pos_filled == idx ) {
+            self->_last_pos_filled -= 1;
+        }
+        return ArrayForTrees__modify(self, NULL);
+    }
+
+    Py_RETURN_NONE;
+}
+
+static PyMappingMethods ArrayForTrees_PyMappingMethods = {
+    (lenfunc) ArrayForTrees___len__,
+    (binaryfunc) ArrayForTrees___getitem__,
+    (objobjargproc) ArrayForTrees___setitem__,
+};
+
+static struct PyMethodDef ArrayForTrees_PyMethodDef[] = {
+    {"fill", (PyCFunction) ArrayForTrees_fill, METH_VARARGS, NULL},
+    {"_modify", (PyCFunction) ArrayForTrees__modify, METH_VARARGS, NULL},
+    {"append", (PyCFunction) ArrayForTrees_append, METH_VARARGS, NULL},
+    {"delete", (PyCFunction) ArrayForTrees_delete, METH_VARARGS, NULL},
+    {NULL}
+};
+
+static struct PyMemberDef ArrayForTrees_PyMemberDef[] = {
+    {"size", T_LONG,
+     offsetof(ArrayForTrees, _size),
+     READONLY, NULL},
+    {"_num", T_LONG,
+     offsetof(ArrayForTrees, _num),
+     READONLY, NULL},
+    {"_last_pos_filled", T_LONG,
+     offsetof(ArrayForTrees, _last_pos_filled),
+     READONLY, NULL},
+    {NULL},
+};
+
+static PyTypeObject ArrayForTreesType = {
+    /* tp_name */ PyVarObject_HEAD_INIT(NULL, 0) "ArrayForTrees",
+    /* tp_basicsize */ sizeof(ArrayForTrees),
+    /* tp_itemsize */ 0,
+    /* tp_dealloc */ (destructor) ArrayForTrees_dealloc,
+    /* tp_print */ 0,
+    /* tp_getattr */ 0,
+    /* tp_setattr */ 0,
+    /* tp_reserved */ 0,
+    /* tp_repr */ 0,
+    /* tp_as_number */ 0,
+    /* tp_as_sequence */ 0,
+    /* tp_as_mapping */ &ArrayForTrees_PyMappingMethods,
+    /* tp_hash  */ 0,
+    /* tp_call */ 0,
+    /* tp_str */ (reprfunc) ArrayForTrees___str__,
+    /* tp_getattro */ 0,
+    /* tp_setattro */ 0,
+    /* tp_as_buffer */ 0,
+    /* tp_flags */ Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE,
+    /* tp_doc */ 0,
+    /* tp_traverse */ 0,
+    /* tp_clear */ 0,
+    /* tp_richcompare */ 0,
+    /* tp_weaklistoffset */ 0,
+    /* tp_iter */ 0,
+    /* tp_iternext */ 0,
+    /* tp_methods */ ArrayForTrees_PyMethodDef,
+    /* tp_members */ ArrayForTrees_PyMemberDef,
+    /* tp_getset */ 0,
+    /* tp_base */ &DynamicArrayType,
+    /* tp_dict */ 0,
+    /* tp_descr_get */ 0,
+    /* tp_descr_set */ 0,
+    /* tp_dictoffset */ 0,
+    /* tp_init */ 0,
+    /* tp_alloc */ 0,
+    /* tp_new */ ArrayForTrees___new__,
+};
+
+#endif
diff --git a/pydatastructs/linear_data_structures/_backend/cpp/arrays/DynamicOneDimensionalArray.hpp b/pydatastructs/linear_data_structures/_backend/cpp/arrays/DynamicOneDimensionalArray.hpp
index 23c8ec811..6715d45c5 100644
--- a/pydatastructs/linear_data_structures/_backend/cpp/arrays/DynamicOneDimensionalArray.hpp
+++ b/pydatastructs/linear_data_structures/_backend/cpp/arrays/DynamicOneDimensionalArray.hpp
@@ -27,25 +27,28 @@ static PyObject* DynamicOneDimensionalArray___new__(PyTypeObject* type, PyObject
                                                     PyObject *kwds) {
     DynamicOneDimensionalArray *self;
     self = reinterpret_cast<DynamicOneDimensionalArray*>(type->tp_alloc(type, 0));
+    if (PyType_Ready(&OneDimensionalArrayType) < 0) { // This has to be present to finalize a type object. This should be called on all type objects to finish their initialization.
+        return NULL;
+    }
     PyObject* _one_dimensional_array = OneDimensionalArray___new__(&OneDimensionalArrayType, args, kwds);
-    if( !_one_dimensional_array ) {
+    if ( !_one_dimensional_array ) {
         return NULL;
     }
     self->_one_dimensional_array = reinterpret_cast<OneDimensionalArray*>(_one_dimensional_array);
     self->_size = (long) self->_one_dimensional_array->_size;
 
     PyObject* _load_factor = PyObject_GetItem(kwds, PyUnicode_FromString("load_factor"));
-    if( _load_factor == nullptr ) {
+    if ( _load_factor == nullptr ) {
         PyErr_Clear();
         self->_load_factor = 0.25;
     } else {
         _load_factor = PyFloat_FromString(PyObject_Str(_load_factor));
-        if( !_load_factor ) {
+        if ( !_load_factor ) {
             return NULL;
         }
         self->_load_factor = PyFloat_AS_DOUBLE(_load_factor);
     }
-    if( self->_one_dimensional_array->_size == 0 ||
+    if ( self->_one_dimensional_array->_size == 0 ||
         self->_one_dimensional_array->_data[0] == Py_None ) {
         self->_num = 0;
     } else {
@@ -82,10 +85,10 @@ static PyObject* DynamicOneDimensionalArray___str__(DynamicOneDimensionalArray *
 static PyObject* DynamicOneDimensionalArray__modify(DynamicOneDimensionalArray *self,
                                                     PyObject* args) {
     PyObject* force = nullptr;
-    if( args ) {
+    if ( args ) {
         force = PyObject_GetItem(args, PyZero);
     }
-    if( !force ) {
+    if ( !force ) {
         PyErr_Clear();
         force = Py_False;
     }
@@ -93,17 +96,17 @@ static PyObject* DynamicOneDimensionalArray__modify(DynamicOneDimensionalArray *
     long i, j;
     PyObject** _data = self->_one_dimensional_array->_data;
     long _size = (long) self->_one_dimensional_array->_size;
-    if( force == Py_True ) {
+    if ( force == Py_True ) {
         i = -1;
         j = _size - 1;
-        while( _data[j] == Py_None) {
+        while ( _data[j] == Py_None) {
             i--;
             j--;
         }
         self->_last_pos_filled = i + _size;
     }
 
-    if( ((float) self->_num)/((float) _size) < self->_load_factor ) {
+    if ( ((float) self->_num)/((float) _size) < self->_load_factor ) {
         long new_size = 2 * self->_num + 1;
         PyObject** arr_new = reinterpret_cast<PyObject**>(std::malloc(new_size * sizeof(PyObject*)));
         for( i = 0; i < new_size; i++ ) {
@@ -112,7 +115,7 @@ static PyObject* DynamicOneDimensionalArray__modify(DynamicOneDimensionalArray *
         }
         long j = 0;
         for( i = 0; i <= self->_last_pos_filled; i++ ) {
-            if( _data[i] != Py_None ) {
+            if ( _data[i] != Py_None ) {
                 Py_INCREF(Py_None);
                 arr_new[j] = _data[i];
                 j += 1;
@@ -130,13 +133,13 @@ static PyObject* DynamicOneDimensionalArray__modify(DynamicOneDimensionalArray *
 static PyObject* DynamicOneDimensionalArray_append(DynamicOneDimensionalArray *self,
                                                     PyObject* args) {
     PyObject* el = PyObject_GetItem(args, PyZero);
-    if( !el ) {
+    if ( !el ) {
         return NULL;
     }
 
     long _size = (long) self->_one_dimensional_array->_size;
     PyObject** _data = self->_one_dimensional_array->_data;
-    if( self->_last_pos_filled + 1 == _size ) {
+    if ( self->_last_pos_filled + 1 == _size ) {
         long new_size = 2 * _size + 1;
         PyObject** arr_new = reinterpret_cast<PyObject**>(std::malloc(new_size * sizeof(PyObject*)));
         long i;
@@ -161,20 +164,20 @@ static PyObject* DynamicOneDimensionalArray_append(DynamicOneDimensionalArray *s
 static PyObject* DynamicOneDimensionalArray_delete(DynamicOneDimensionalArray *self,
                                                    PyObject* args) {
     PyObject* idx_pyobject = PyObject_GetItem(args, PyZero);
-    if( !idx_pyobject ) {
+    if ( !idx_pyobject ) {
         return NULL;
     }
     long idx = PyLong_AsLong(idx_pyobject);
-    if( idx == -1 && PyErr_Occurred() ) {
+    if ( idx == -1 && PyErr_Occurred() ) {
         return NULL;
     }
 
     PyObject** _data = self->_one_dimensional_array->_data;
-    if( idx <= self->_last_pos_filled && idx >= 0 &&
+    if ( idx <= self->_last_pos_filled && idx >= 0 &&
         _data[idx] != Py_None ) {
         _data[idx] = Py_None;
         self->_num -= 1;
-        if( self->_last_pos_filled == idx ) {
+        if ( self->_last_pos_filled == idx ) {
             self->_last_pos_filled -= 1;
         }
         return DynamicOneDimensionalArray__modify(self, NULL);
diff --git a/pydatastructs/linear_data_structures/_backend/cpp/arrays/OneDimensionalArray.hpp b/pydatastructs/linear_data_structures/_backend/cpp/arrays/OneDimensionalArray.hpp
index e78fc2ed0..525dc8471 100644
--- a/pydatastructs/linear_data_structures/_backend/cpp/arrays/OneDimensionalArray.hpp
+++ b/pydatastructs/linear_data_structures/_backend/cpp/arrays/OneDimensionalArray.hpp
@@ -27,14 +27,14 @@ static PyObject* OneDimensionalArray___new__(PyTypeObject* type, PyObject *args,
     size_t len_args = PyObject_Length(args);
 
     PyObject *dtype = PyObject_GetItem(args, PyZero);
-    if( dtype == Py_None ) {
+    if ( dtype == Py_None ) {
         PyErr_SetString(PyExc_ValueError,
                         "Data type is not defined.");
         return NULL;
     }
     self->_dtype = dtype;
 
-    if( len_args != 2 && len_args != 3 ) {
+    if ( len_args != 2 && len_args != 3 ) {
         PyErr_SetString(PyExc_ValueError,
                         "Too few arguments to create a 1D array,"
                         " pass either size of the array"
@@ -42,16 +42,16 @@ static PyObject* OneDimensionalArray___new__(PyTypeObject* type, PyObject *args,
         return NULL;
     }
 
-    if( len_args == 3 ) {
+    if ( len_args == 3 ) {
         PyObject *args0 = PyObject_GetItem(args, PyOne);
         PyObject *args1 = PyObject_GetItem(args, PyTwo);
         size_t size;
         PyObject *data = NULL;
-        if( (PyList_Check(args0) || PyTuple_Check(args0)) &&
+        if ( (PyList_Check(args0) || PyTuple_Check(args0)) &&
              PyLong_Check(args1) ) {
             size = PyLong_AsUnsignedLong(args1);
             data = args0;
-        } else if( (PyList_Check(args1) || PyTuple_Check(args1)) &&
+        } else if ( (PyList_Check(args1) || PyTuple_Check(args1)) &&
                     PyLong_Check(args0) ) {
             size = PyLong_AsUnsignedLong(args0);
             data = args1;
@@ -62,7 +62,7 @@ static PyObject* OneDimensionalArray___new__(PyTypeObject* type, PyObject *args,
             return NULL;
         }
         size_t len_data = PyObject_Length(data);
-        if( size != len_data ) {
+        if ( size != len_data ) {
             PyErr_Format(PyExc_ValueError,
                          "Conflict in the size, %d and length of data, %d",
                          size, len_data);
@@ -72,32 +72,32 @@ static PyObject* OneDimensionalArray___new__(PyTypeObject* type, PyObject *args,
         self->_data = reinterpret_cast<PyObject**>(std::malloc(size * sizeof(PyObject*)));
         for( size_t i = 0; i < size; i++ ) {
             PyObject* value = PyObject_GetItem(data, PyLong_FromSize_t(i));
-            if( raise_exception_if_dtype_mismatch(value, self->_dtype) ) {
+            if ( raise_exception_if_dtype_mismatch(value, self->_dtype) ) {
                 return NULL;
             }
             self->_data[i] = value;
         }
-    } else if( len_args == 2 ) {
+    } else if ( len_args == 2 ) {
         PyObject *args0 = PyObject_GetItem(args, PyOne);
-        if( PyLong_Check(args0) ) {
+        if ( PyLong_Check(args0) ) {
             self->_size = PyLong_AsSize_t(args0);
             PyObject* init = PyObject_GetItem(kwds, PyUnicode_FromString("init"));
-            if( init == nullptr ) {
+            if ( init == nullptr ) {
                 PyErr_Clear();
                 init = Py_None;
-            } else if( raise_exception_if_dtype_mismatch(init, self->_dtype) ) {
+            } else if ( raise_exception_if_dtype_mismatch(init, self->_dtype) ) {
                 return NULL;
             }
             self->_data = reinterpret_cast<PyObject**>(std::malloc(self->_size * sizeof(PyObject*)));
             for( size_t i = 0; i < self->_size; i++ ) {
                 self->_data[i] = init;
             }
-        } else if( (PyList_Check(args0) || PyTuple_Check(args0)) ) {
+        } else if ( (PyList_Check(args0) || PyTuple_Check(args0)) ) {
             self->_size = PyObject_Length(args0);
             self->_data = reinterpret_cast<PyObject**>(std::malloc(self->_size * sizeof(PyObject*)));
             for( size_t i = 0; i < self->_size; i++ ) {
                 PyObject* value = PyObject_GetItem(args0, PyLong_FromSize_t(i));
-                if( raise_exception_if_dtype_mismatch(value, self->_dtype) ) {
+                if ( raise_exception_if_dtype_mismatch(value, self->_dtype) ) {
                     return NULL;
                 }
                 self->_data[i] = value;
@@ -109,14 +109,13 @@ static PyObject* OneDimensionalArray___new__(PyTypeObject* type, PyObject *args,
             return NULL;
         }
     }
-
     return reinterpret_cast<PyObject*>(self);
 }
 
 static PyObject* OneDimensionalArray___getitem__(OneDimensionalArray *self,
                                                  PyObject* arg) {
     size_t idx = PyLong_AsUnsignedLong(arg);
-    if( idx >= self->_size ) {
+    if ( idx >= self->_size ) {
         PyErr_Format(PyExc_IndexError,
                      "Index, %d, out of range, [%d, %d)",
                      idx, 0, self->_size);
@@ -129,9 +128,9 @@ static PyObject* OneDimensionalArray___getitem__(OneDimensionalArray *self,
 static int OneDimensionalArray___setitem__(OneDimensionalArray *self,
                                                  PyObject* arg, PyObject* value) {
     size_t idx = PyLong_AsUnsignedLong(arg);
-    if( value == Py_None ) {
+    if ( value == Py_None ) {
         self->_data[idx] = value;
-    } else if( !set_exception_if_dtype_mismatch(value, self->_dtype) ) {
+    } else if ( !set_exception_if_dtype_mismatch(value, self->_dtype) ) {
         self->_data[idx] = value;
     }
     return 0;
@@ -139,7 +138,7 @@ static int OneDimensionalArray___setitem__(OneDimensionalArray *self,
 
 static PyObject* OneDimensionalArray_fill(OneDimensionalArray *self, PyObject *args) {
     PyObject* value = PyObject_GetItem(args, PyZero);
-    if( raise_exception_if_dtype_mismatch(value, self->_dtype) ) {
+    if ( raise_exception_if_dtype_mismatch(value, self->_dtype) ) {
         return NULL;
     }
 
diff --git a/pydatastructs/linear_data_structures/_backend/cpp/arrays/arrays.cpp b/pydatastructs/linear_data_structures/_backend/cpp/arrays/arrays.cpp
index a8a3cc9ba..974f38b5b 100644
--- a/pydatastructs/linear_data_structures/_backend/cpp/arrays/arrays.cpp
+++ b/pydatastructs/linear_data_structures/_backend/cpp/arrays/arrays.cpp
@@ -3,6 +3,7 @@
 #include "OneDimensionalArray.hpp"
 #include "DynamicArray.hpp"
 #include "DynamicOneDimensionalArray.hpp"
+#include "ArrayForTrees.hpp"
 
 static struct PyModuleDef arrays_struct = {
     PyModuleDef_HEAD_INIT,
@@ -40,5 +41,11 @@ PyMODINIT_FUNC PyInit__arrays(void) {
     Py_INCREF(&DynamicOneDimensionalArrayType);
     PyModule_AddObject(arrays, "DynamicOneDimensionalArray", reinterpret_cast<PyObject*>(&DynamicOneDimensionalArrayType));
 
+    if (PyType_Ready(&ArrayForTreesType) < 0) {
+        return NULL;
+    }
+    Py_INCREF(&ArrayForTreesType);
+    PyModule_AddObject(arrays, "ArrayForTrees", reinterpret_cast<PyObject*>(&ArrayForTreesType));
+
     return arrays;
 }
diff --git a/pydatastructs/miscellaneous_data_structures/_backend/cpp/stack/ArrayStack.hpp b/pydatastructs/miscellaneous_data_structures/_backend/cpp/stack/ArrayStack.hpp
index 5b51d0d4c..eb4a27fe0 100644
--- a/pydatastructs/miscellaneous_data_structures/_backend/cpp/stack/ArrayStack.hpp
+++ b/pydatastructs/miscellaneous_data_structures/_backend/cpp/stack/ArrayStack.hpp
@@ -113,7 +113,7 @@ static Py_ssize_t ArrayStack__len__(ArrayStack *self) {
     return self->_items->_num;
 }
 
-static PyObject* ArrayStack__str__(ArrayStack* self){
+static PyObject* ArrayStack__str__(ArrayStack* self) {
     return DynamicOneDimensionalArray___str__(self->_items);
 }
 
diff --git a/pydatastructs/trees/__init__.py b/pydatastructs/trees/__init__.py
index 6b9df8a22..1c99cca25 100644
--- a/pydatastructs/trees/__init__.py
+++ b/pydatastructs/trees/__init__.py
@@ -4,7 +4,8 @@
     binary_trees,
     m_ary_trees,
     space_partitioning_trees,
-    heaps
+    heaps,
+    _extensions
 )
 
 from .binary_trees import (
diff --git a/pydatastructs/trees/_backend/cpp/BinarySearchTree.hpp b/pydatastructs/trees/_backend/cpp/BinarySearchTree.hpp
new file mode 100644
index 000000000..0a920db87
--- /dev/null
+++ b/pydatastructs/trees/_backend/cpp/BinarySearchTree.hpp
@@ -0,0 +1,722 @@
+#ifndef TREES_BINARYSEARCHTREE_HPP
+#define TREES_BINARYSEARCHTREE_HPP
+
+#define PY_SSIZE_T_CLEAN
+#include <Python.h>
+#include <structmember.h>
+#include <cstdlib>
+#include <stack>
+#include "../../../utils/_backend/cpp/utils.hpp"
+#include "../../../utils/_backend/cpp/TreeNode.hpp"
+#include "../../../linear_data_structures/_backend/cpp/arrays/ArrayForTrees.hpp"
+#include "BinaryTree.hpp"
+
+typedef struct {
+    PyObject_HEAD
+    BinaryTree* binary_tree;
+    ArrayForTrees* tree;
+} BinarySearchTree;
+
+static void BinarySearchTree_dealloc(BinarySearchTree *self) {
+    BinaryTree_dealloc(self->binary_tree);
+    Py_TYPE(self)->tp_free(reinterpret_cast<PyObject*>(self));
+}
+
+static PyObject* BinarySearchTree___new__(PyTypeObject* type, PyObject *args, PyObject *kwds) {
+    BinarySearchTree *self;
+    self = reinterpret_cast<BinarySearchTree*>(type->tp_alloc(type, 0));
+
+    if (PyType_Ready(&BinaryTreeType) < 0) { // This has to be present to finalize a type object. This should be called on all type objects to finish their initialization.
+        return NULL;
+    }
+    PyObject* bt = BinaryTree___new__(&BinaryTreeType, args, kwds);
+    self->binary_tree = reinterpret_cast<BinaryTree*>(bt);
+    self->tree = reinterpret_cast<BinaryTree*>(bt)->tree;
+
+    return reinterpret_cast<PyObject*>(self);
+}
+
+static PyObject* BinarySearchTree___str__(BinarySearchTree *self) {
+    return BinaryTree___str__(self->binary_tree);
+}
+
+static long BinarySearchTree_left_size(BinarySearchTree* self, TreeNode* node) {
+    if (node->left != Py_None) {
+        TreeNode* n = reinterpret_cast<TreeNode*>(
+            self->binary_tree->tree->_one_dimensional_array->_data[PyLong_AsLong(node->left)]
+        );
+        return n->size;
+    } else {
+        return 0;
+    }
+}
+
+static long BinarySearchTree_right_size(BinarySearchTree* self, TreeNode* node) {
+    if (node->right != Py_None) {
+        TreeNode* n = reinterpret_cast<TreeNode*>(
+            self->binary_tree->tree->_one_dimensional_array->_data[PyLong_AsLong(node->right)]
+        );
+        return n->size;
+    } else {
+        return 0;
+    }
+}
+
+static PyObject* BinarySearchTree__update_size(BinarySearchTree* self, PyObject *args) {
+    PyObject *start_idx = PyObject_GetItem(args, PyZero);
+    if (self->binary_tree->is_order_statistic) {
+        PyObject* walk = start_idx;
+        while (walk!=Py_None) {
+            TreeNode* node = reinterpret_cast<TreeNode*>(self->binary_tree->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)]);
+            node->size = BinarySearchTree_left_size(self, node) + BinarySearchTree_right_size(self, node) + 1;
+            walk = node->parent;
+        }
+    }
+    Py_RETURN_NONE;
+}
+
+static PyObject* BinarySearchTree_search(BinarySearchTree* self, PyObject* args, PyObject *kwds) {
+    Py_INCREF(Py_None);
+    PyObject* ret_parent = Py_None;
+    PyObject* key;
+    static char* keywords[] = {"key","parent", NULL};
+    if (!PyArg_ParseTupleAndKeywords(args, kwds, "O|O", keywords, &key, &ret_parent)) { // ret_parent is optional
+        return NULL;
+    }
+    BinaryTree* bt = self->binary_tree;
+    PyObject* parent = Py_None;
+    PyObject* walk = PyLong_FromLong(PyLong_AsLong(bt->root_idx));
+
+    if (reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->key == Py_None) {
+        Py_RETURN_NONE;
+    }
+
+    while (walk != Py_None) {
+        PyObject* curr_key = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->key;
+
+        if (curr_key == key) {
+            break;
+        }
+        parent = walk;
+
+        if (!PyCallable_Check(bt->comparator)) {
+            PyErr_SetString(PyExc_ValueError, "comparator should be callable");
+            return NULL;
+        }
+        PyObject* arguments = Py_BuildValue("OO", key, curr_key);
+        PyObject* res = PyObject_CallObject(bt->comparator, arguments);
+        Py_DECREF(arguments);
+        if (!PyLong_Check(res)) {
+            PyErr_SetString(PyExc_TypeError, "bad return type from comparator");
+            return NULL;
+        }
+        long long comp = PyLong_AsLongLong(res);
+
+        if (comp == 1) {
+            walk = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->left;
+        }
+        else {
+            walk = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->right;
+        }
+    }
+
+    Py_INCREF(Py_None);
+    if (ret_parent==Py_None || PyLong_AsLong(ret_parent)==0) {
+        return walk;
+    }
+    else {
+        return Py_BuildValue("OO",walk,parent);
+    }
+    Py_RETURN_NONE; // dummy return statement, never executed
+}
+
+static PyObject* BinarySearchTree_insert(BinarySearchTree* self, PyObject* args) {
+    Py_INCREF(Py_None);
+    PyObject* key = Py_None;
+    Py_INCREF(Py_None);
+    PyObject* data = Py_None;
+    if (!PyArg_ParseTuple(args, "O|O", &key, &data)) { // ret_parent is optional
+        return NULL;
+    }
+
+    PyObject* parent = PyLong_FromLong(0);
+
+    PyObject* res = BinarySearchTree_search(self, Py_BuildValue("(O)",key), PyDict_New()); // keywords should be a dictionary, so empty dictionary here as no keywords
+    BinaryTree* bt = self->binary_tree;
+    if (res != Py_None) {
+        reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(res)])->data = data;
+        Py_RETURN_NONE;
+    }
+
+    PyObject* walk = PyLong_FromLong(PyLong_AsLong(bt->root_idx));
+    if (reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->key == Py_None) {
+        reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->key = key;
+        reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->data = data;
+        Py_RETURN_NONE;
+    }
+
+    if (PyType_Ready(&TreeNodeType) < 0) { // This has to be present to finalize a type object. This should be called on all type objects to finish their initialization.
+        return NULL;
+    }
+    TreeNode* new_node = reinterpret_cast<TreeNode*>(TreeNode___new__(&TreeNodeType, Py_BuildValue("(OO)", key, data), PyDict_New()));
+    PyObject* prev_node = PyLong_FromLong(PyLong_AsLong(bt->root_idx));
+    bool flag = true;
+
+    while (flag) {
+        PyObject* curr_key = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->key;
+        if (!PyCallable_Check(bt->comparator)) {
+            PyErr_SetString(PyExc_ValueError, "comparator should be callable");
+            return NULL;
+        }
+        PyObject* arguments = Py_BuildValue("OO", key, curr_key);
+        PyObject* cres = PyObject_CallObject(bt->comparator, arguments);
+        Py_DECREF(arguments);
+        if (!PyLong_Check(cres)) {
+            PyErr_SetString(PyExc_TypeError, "bad return type from comparator");
+            return NULL;
+        }
+        long long comp = PyLong_AsLongLong(cres);
+
+        if (comp==0) {
+            if (reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->right == Py_None) {
+                new_node->parent = prev_node;
+                ArrayForTrees_append(bt->tree, Py_BuildValue( "[O]", reinterpret_cast<PyObject*>(new_node)) );
+                reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->right = PyLong_FromLong(bt->size);
+                bt->size = bt->size + 1;
+                flag = false;
+            }
+            prev_node = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->right;
+            walk = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->right;
+        }
+        else {
+            if (reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->left == Py_None) {
+                new_node->parent = prev_node;
+                ArrayForTrees_append(bt->tree, Py_BuildValue( "[O]", reinterpret_cast<PyObject*>(new_node)) );
+                reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->left = PyLong_FromLong(bt->size);
+                bt->size = bt->size + 1;
+                flag = false;
+            }
+            prev_node = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->left;
+            walk = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->left;
+        }
+    }
+    BinarySearchTree__update_size(self, Py_BuildValue("(O)",walk));
+    Py_RETURN_NONE;
+}
+
+static PyObject* BinarySearchTree_delete(BinarySearchTree* self, PyObject *args, PyObject *kwds) {
+    Py_INCREF(Py_None);
+    PyObject* key = Py_None;
+    Py_INCREF(Py_None);
+    PyObject* balancing_info = Py_None;
+    static char* keywords[] = {"key","balancing_info", NULL};
+    if (!PyArg_ParseTupleAndKeywords(args, kwds, "O|O", keywords, &key, &balancing_info)) {
+        return NULL;
+    }
+    PyObject* kwd_parent = PyDict_New();
+    PyDict_SetItemString(kwd_parent, "parent", PyLong_FromLong(1));
+    PyObject* tup = BinarySearchTree_search(self, Py_BuildValue("(O)",key), kwd_parent);
+    PyObject* walk = PyTuple_GetItem(tup, 0);
+    PyObject* parent = PyTuple_GetItem(tup, 1);
+    Py_INCREF(Py_None);
+    PyObject* a = Py_None;
+    if (walk == Py_None) {
+        Py_RETURN_NONE;
+    }
+    BinaryTree* bt = self->binary_tree;
+    if (reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->left == Py_None && reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->right == Py_None) {
+        if (parent == Py_None) {
+            reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(bt->root_idx)])->data = Py_None;
+            reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(bt->root_idx)])->key = Py_None;
+        }
+        else {
+            if (reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(parent)])->left == walk) {
+                Py_INCREF(Py_None);
+                reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(parent)])->left = Py_None;
+            }
+            else {
+                Py_INCREF(Py_None);
+                reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(parent)])->right = Py_None;
+            }
+            a = parent;
+            PyObject* par_key = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(parent)])->key;
+            PyObject* root_key = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(bt->root_idx)])->key;
+            PyObject* new_indices = ArrayForTrees_delete(bt->tree, Py_BuildValue("(O)",walk));
+            if (new_indices != Py_None) {
+                a = PyDict_GetItem(new_indices, par_key);
+                bt->root_idx = PyDict_GetItem(new_indices, root_key);
+            }
+        }
+        BinarySearchTree__update_size(self, Py_BuildValue("(O)",a));
+    }
+    else if (reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->left != Py_None && reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->right != Py_None) {
+        PyObject* twalk = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->right;
+        PyObject* par = walk;
+        bool flag = false;
+        while (reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(twalk)])->left != Py_None) {
+            flag = true;
+            par = twalk;
+            twalk = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(twalk)])->left;
+        }
+        reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->data = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(twalk)])->data;
+        reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->key = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(twalk)])->key;
+        if (flag) {
+            reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(par)])->left = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(twalk)])->right;
+        }
+        else {
+            reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(par)])->right = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(twalk)])->right;
+        }
+
+        if (reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(twalk)])->right != Py_None) {
+            reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(twalk)])->right)])->parent = par;
+        }
+
+        if (twalk != Py_None) {
+            a = par;
+            PyObject* par_key = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(par)])->key;
+            PyObject* root_key = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(bt->root_idx)])->key;
+            PyObject* new_indices = ArrayForTrees_delete(bt->tree, Py_BuildValue("(O)",twalk));
+            if (new_indices != Py_None) {
+                a = PyDict_GetItem(new_indices, par_key);
+                bt->root_idx = PyDict_GetItem(new_indices, root_key);
+            }
+        }
+        BinarySearchTree__update_size(self, Py_BuildValue("(O)",a));
+    }
+    else {
+        PyObject* child;
+        if (reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->left != Py_None) {
+            child = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->left;
+        }
+        else {
+            child = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->right;
+        }
+        if (parent == Py_None) {
+            reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(bt->root_idx)])->left = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(child)])->left;
+            reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(bt->root_idx)])->right = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(child)])->right;
+            reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(bt->root_idx)])->data = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(child)])->data;
+            reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(bt->root_idx)])->key = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(child)])->key;
+            Py_INCREF(Py_None);
+            reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(bt->root_idx)])->parent = Py_None;
+            PyObject* root_key = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(bt->root_idx)])->key;
+            PyObject* new_indices = ArrayForTrees_delete(bt->tree, Py_BuildValue("(O)",child));
+            if (new_indices != Py_None) {
+                bt->root_idx = PyDict_GetItem(new_indices, root_key);
+            }
+        }
+        else {
+            if (reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(parent)])->left == walk) {
+                reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(parent)])->left = child;
+            }
+            else {
+                reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(parent)])->right = child;
+            }
+            reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(child)])->parent = parent;
+            a = parent;
+            PyObject* par_key = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(parent)])->key;
+            PyObject* root_key = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(bt->root_idx)])->key;
+            PyObject* new_indices = ArrayForTrees_delete(bt->tree, Py_BuildValue("(O)",walk));
+            if (new_indices != Py_None) {
+                parent = PyDict_GetItem(new_indices, par_key);
+                reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(child)])->parent = PyDict_GetItem(new_indices, root_key);
+                a = PyDict_GetItem(new_indices, root_key);
+                bt->root_idx = PyDict_GetItem(new_indices, root_key);
+            }
+            BinarySearchTree__update_size(self, Py_BuildValue("(O)",a));
+        }
+    }
+
+    if (balancing_info != Py_None) {
+        if (PyLong_AsLong(balancing_info) == 1) {
+            return a;
+        }
+    }
+    Py_RETURN_TRUE;
+}
+
+static PyObject* BinarySearchTree__bound_helper(BinarySearchTree* self, PyObject *args) {
+    // This function is only called internally, so all arguments are passed in proper order
+    PyObject *node_idx = PyObject_GetItem(args, PyZero);
+    PyObject *bound_key = PyObject_GetItem(args, PyOne);
+    PyObject *is_upper = PyObject_GetItem(args, PyTwo);
+    BinaryTree* bt = self->binary_tree;
+    if (node_idx == Py_None) {
+        Py_RETURN_NONE;
+    }
+    if (reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(node_idx)])->key == Py_None) {
+        Py_RETURN_NONE;
+    }
+    if (reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(node_idx)])->key == bound_key) {
+        if (is_upper == Py_False) {
+            return reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(node_idx)])->key;
+        }
+        else {
+            return BinarySearchTree__bound_helper(self, Py_BuildValue("(OOO)",reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(node_idx)])->right, bound_key, is_upper));
+        }
+    }
+
+    if (!PyCallable_Check(bt->comparator)) {
+        PyErr_SetString(PyExc_ValueError, "comparator should be callable");
+        return NULL;
+    }
+    PyObject* arguments = Py_BuildValue("OO", reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(node_idx)])->key, bound_key);
+    PyObject* cres = PyObject_CallObject(bt->comparator, arguments);
+    Py_DECREF(arguments);
+    if (!PyLong_Check(cres)) {
+        PyErr_SetString(PyExc_TypeError, "bad return type from comparator");
+        return NULL;
+    }
+    long long comp = PyLong_AsLongLong(cres);
+
+    if (comp == 1) {
+        return BinarySearchTree__bound_helper(self, Py_BuildValue("(OOO)",reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(node_idx)])->right, bound_key, is_upper));
+    }
+    else {
+        PyObject* res_bound = BinarySearchTree__bound_helper(self, Py_BuildValue("(OOO)",reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(node_idx)])->left, bound_key, is_upper));
+        if (res_bound != Py_None) {
+            return res_bound;
+        }
+        else {
+            return reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(node_idx)])->key;
+        }
+    }
+}
+
+static PyObject* BinarySearchTree_lower_bound(BinarySearchTree* self, PyObject *args, PyObject* kwds) {
+    PyObject* key = PyObject_GetItem(args, PyZero);
+    return BinarySearchTree__bound_helper(self, Py_BuildValue("(OOO)", self->binary_tree->root_idx, key, Py_False));
+}
+
+static PyObject* BinarySearchTree_upper_bound(BinarySearchTree* self, PyObject *args, PyObject* kwds) {
+    PyObject* key = PyObject_GetItem(args, PyZero);
+    return BinarySearchTree__bound_helper(self, Py_BuildValue("(OOO)", self->binary_tree->root_idx, key, Py_True));
+}
+
+static PyObject* BinarySearchTree__simple_path(BinarySearchTree* self, PyObject *args) {
+    PyObject* key = PyObject_GetItem(args, PyZero);
+    PyObject* root = PyObject_GetItem(args, PyOne);
+    std::stack<long> stack;
+    stack.push(PyLong_AsLong(root));
+    PyObject* path = PyList_New(0);
+    long node_idx = -1;
+    BinaryTree* bt = self->binary_tree;
+
+    while (!stack.empty()) {
+        long node = stack.top();
+        stack.pop();
+        if (reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[node])->key == key) {
+            node_idx = node;
+            break;
+        }
+        if (reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[node])->left != Py_None) {
+            stack.push(PyLong_AsLong(reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[node])->left));
+        }
+        if (reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[node])->right != Py_None) {
+            stack.push(PyLong_AsLong(reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[node])->right));
+        }
+    }
+    if (node_idx == -1) {
+        return path;
+    }
+    while (node_idx != 0) {
+        PyList_Append(path, PyLong_FromLong(node_idx));
+        node_idx = PyLong_AsLong(reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[node_idx])->parent);
+    }
+    PyList_Append(path, PyLong_FromLong(0));
+    PyList_Reverse(path);
+    return path;
+}
+
+static PyObject* BinarySearchTree__lca_1(BinarySearchTree* self, PyObject* args) {
+    long j = PyLong_AsLong(PyObject_GetItem(args, PyZero));
+    long k = PyLong_AsLong(PyObject_GetItem(args, PyOne));
+    BinaryTree* bt = self->binary_tree;
+    PyObject* root = bt->root_idx;
+    PyObject* path1 = BinarySearchTree__simple_path(self, Py_BuildValue("(OO)",PyLong_FromLong(j),root));
+    PyObject* path2 = BinarySearchTree__simple_path(self, Py_BuildValue("(OO)",PyLong_FromLong(k),root));
+    long n = PyLong_AsLong(PyLong_FromSsize_t(PyList_Size(path1)));
+    long m = PyLong_AsLong(PyLong_FromSsize_t(PyList_Size(path2)));
+    if (n==0 || m==0) {
+        PyErr_SetString(PyExc_ValueError, "One of the two paths doesn't exist.");
+        return NULL;
+    }
+    long i = 0;
+    j = 0;
+    while (i<n && j<m) {
+        if (PyList_GetItem(path1, PyLong_AsSsize_t(PyLong_FromLong(i))) != PyList_GetItem(path2, PyLong_AsSsize_t(PyLong_FromLong(j)))) {
+            return reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(PyList_GetItem(path1, PyLong_AsSsize_t(PyLong_FromLong(i-1))))])->key;
+        }
+        i += 1;
+        j += 1;
+    }
+
+    while (i<n && j<m) {
+        if (PyList_GetItem(path1, PyLong_AsSsize_t(PyLong_FromLong(i))) < PyList_GetItem(path2, PyLong_AsSsize_t(PyLong_FromLong(j)))) {
+            return reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(PyList_GetItem(path1, PyLong_AsSsize_t(PyLong_FromLong(n-1))))])->key;
+        }
+        else if (PyList_GetItem(path1, PyLong_AsSsize_t(PyLong_FromLong(i))) > PyList_GetItem(path2, PyLong_AsSsize_t(PyLong_FromLong(j)))) {
+            break;
+        }
+        i += 1;
+        j += 1;
+    }
+    return reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(PyList_GetItem(path2, PyLong_AsSsize_t(PyLong_FromLong(m-1))))])->key;
+}
+
+static PyObject* BinarySearchTree__lca_2(BinarySearchTree* self, PyObject* args) {
+    PyObject* j = PyObject_GetItem(args, PyZero);
+    PyObject* k = PyObject_GetItem(args, PyOne);
+    BinaryTree* bt = self->binary_tree;
+
+    PyObject* curr_root = bt->root_idx;
+    PyObject* u = BinarySearchTree_search(self, Py_BuildValue("(O)",j), PyDict_New());
+    PyObject* v = BinarySearchTree_search(self, Py_BuildValue("(O)",k), PyDict_New());
+
+    if (u==Py_None || v==Py_None) {
+        PyErr_SetString(PyExc_ValueError, "One of the nodes doesn't exist.");
+        return NULL;
+    }
+
+    if (!PyCallable_Check(bt->comparator)) {
+        PyErr_SetString(PyExc_ValueError, "comparator should be callable");
+        return NULL;
+    }
+    PyObject* arguments1 = Py_BuildValue("OO", reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(u)])->key, reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(curr_root)])->key);
+    PyObject* cres1 = PyObject_CallObject(bt->comparator, arguments1);
+    Py_DECREF(arguments1);
+    if (!PyLong_Check(cres1)) {
+        PyErr_SetString(PyExc_TypeError, "bad return type from comparator");
+        return NULL;
+    }
+    long long u_left = PyLong_AsLongLong(cres1);
+
+    if (!PyCallable_Check(bt->comparator)) {
+        PyErr_SetString(PyExc_ValueError, "comparator should be callable");
+        return NULL;
+    }
+    PyObject* arguments2 = Py_BuildValue("OO", reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(v)])->key, reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(curr_root)])->key);
+    PyObject* cres2 = PyObject_CallObject(bt->comparator, arguments2);
+    Py_DECREF(arguments2);
+    if (!PyLong_Check(cres2)) {
+        PyErr_SetString(PyExc_TypeError, "bad return type from comparator");
+        return NULL;
+    }
+    long long v_left = PyLong_AsLongLong(cres2);
+
+    while (!(u_left ^ v_left)) {
+        if (u_left && v_left) {
+            curr_root = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(curr_root)])->left;
+        }
+        else {
+            curr_root = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(curr_root)])->right;
+        }
+
+        if (curr_root == u || curr_root == v) {
+            if (curr_root == Py_None) {
+                Py_RETURN_NONE;
+            }
+            return reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(curr_root)])->key;
+        }
+
+        if (!PyCallable_Check(bt->comparator)) {
+            PyErr_SetString(PyExc_ValueError, "comparator should be callable");
+            return NULL;
+        }
+        PyObject* arguments1 = Py_BuildValue("OO", reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(u)])->key, reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(curr_root)])->key);
+        PyObject* cres1 = PyObject_CallObject(bt->comparator, arguments1);
+        Py_DECREF(arguments1);
+        if (!PyLong_Check(cres1)) {
+            PyErr_SetString(PyExc_TypeError, "bad return type from comparator");
+            return NULL;
+        }
+        u_left = PyLong_AsLongLong(cres1);
+
+        if (!PyCallable_Check(bt->comparator)) {
+            PyErr_SetString(PyExc_ValueError, "comparator should be callable");
+            return NULL;
+        }
+        PyObject* arguments2 = Py_BuildValue("OO", reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(v)])->key, reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(curr_root)])->key);
+        PyObject* cres2 = PyObject_CallObject(bt->comparator, arguments2);
+        Py_DECREF(arguments2);
+        if (!PyLong_Check(cres2)) {
+            PyErr_SetString(PyExc_TypeError, "bad return type from comparator");
+            return NULL;
+        }
+        v_left = PyLong_AsLongLong(cres2);
+    }
+
+    if (curr_root == Py_None) {
+        Py_RETURN_NONE;
+    }
+    return reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(curr_root)])->key;
+}
+
+static PyObject* BinarySearchTree_lowest_common_ancestor(BinarySearchTree* self, PyObject* args) {
+    Py_INCREF(Py_None);
+    PyObject* j = Py_None;
+    Py_INCREF(Py_None);
+    PyObject* k = Py_None;
+    PyObject* algorithm = PyOne;
+    if (!PyArg_ParseTuple(args, "OO|O", &j, &k, &algorithm)) { // ret_parent is optional
+        return NULL;
+    }
+
+    if (algorithm == PyOne) {
+        return BinarySearchTree__lca_1(self, Py_BuildValue("(OO)",j,k));
+    }
+    else {
+        return BinarySearchTree__lca_2(self, Py_BuildValue("(OO)",j,k));
+    }
+}
+
+static PyObject* BinarySearchTree_rank(BinarySearchTree* self, PyObject* args) {
+    PyObject* x = PyObject_GetItem(args, PyZero);
+    PyObject* walk = BinarySearchTree_search(self, Py_BuildValue("(O)",x), PyDict_New());
+    if (walk == Py_None) {
+        Py_RETURN_NONE;
+    }
+    BinaryTree* bt = self->binary_tree;
+    long r = BinarySearchTree_left_size(self, reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])) + 1;
+    while (reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->key != reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(bt->root_idx)])->key) {
+        PyObject* p = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->parent;
+        if (walk == reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(p)])->right) {
+            r = r + BinarySearchTree_left_size(self, reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(p)])) + 1;
+        }
+        walk = p;
+    }
+    return PyLong_FromLong(r);
+}
+
+static PyObject* BinarySearchTree_select(BinarySearchTree* self, PyObject* args) {
+    long i = PyLong_AsLong(PyObject_GetItem(args, PyZero));
+    i = i - 1;
+    if (i < 0) {
+        PyErr_SetString(PyExc_ValueError, "Expected a positive integer");
+        return NULL;
+    }
+    BinaryTree* bt = self->binary_tree;
+    if (i >= bt->tree->_num) {
+        PyErr_SetString(PyExc_ValueError, "Integer passed to select() is greater than the size of the tree.");
+        return NULL;
+    }
+    PyObject* walk = bt->root_idx;
+    while (walk != Py_None) {
+        long l = BinarySearchTree_left_size(self, reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)]));
+        if (i == l) {
+            return bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)];
+        }
+        PyObject* left_walk = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->left;
+        PyObject* right_walk = reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->right;
+        if (left_walk == Py_None && right_walk==Py_None) {
+            PyErr_SetString(PyExc_IndexError, "The traversal is terminated due to no child nodes ahead.");
+            return NULL;
+        }
+        if (i < l) {
+            if (!PyCallable_Check(bt->comparator)) {
+                PyErr_SetString(PyExc_ValueError, "comparator should be callable");
+                return NULL;
+            }
+            PyObject* arguments = Py_BuildValue("OO", reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(left_walk)])->key, reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->key);
+            PyObject* cres = PyObject_CallObject(bt->comparator, arguments);
+            Py_DECREF(arguments);
+            if (!PyLong_Check(cres)) {
+                PyErr_SetString(PyExc_TypeError, "bad return type from comparator");
+                return NULL;
+            }
+            long long comp = PyLong_AsLongLong(cres);
+
+            if (left_walk != Py_None && comp) {
+                walk = left_walk;
+            }
+            else {
+                walk = right_walk;
+            }
+        }
+        else {
+            if (!PyCallable_Check(bt->comparator)) {
+                PyErr_SetString(PyExc_ValueError, "comparator should be callable");
+                return NULL;
+            }
+            PyObject* arguments = Py_BuildValue("OO", reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(right_walk)])->key, reinterpret_cast<TreeNode*>(bt->tree->_one_dimensional_array->_data[PyLong_AsLong(walk)])->key);
+            PyObject* cres = PyObject_CallObject(bt->comparator, arguments);
+            Py_DECREF(arguments);
+            if (!PyLong_Check(cres)) {
+                PyErr_SetString(PyExc_TypeError, "bad return type from comparator");
+                return NULL;
+            }
+            long long comp = PyLong_AsLongLong(cres);
+
+            if (right_walk != Py_None && (!comp)) {
+                walk = right_walk;
+            }
+            else {
+                walk = left_walk;
+            }
+            i = i - (l + 1);
+        }
+    }
+    Py_RETURN_NONE; // dummy return statement, never executed
+}
+
+static struct PyMethodDef BinarySearchTree_PyMethodDef[] = {
+    {"insert", (PyCFunction) BinarySearchTree_insert, METH_VARARGS | METH_KEYWORDS, NULL},
+    {"delete", (PyCFunction) BinarySearchTree_delete, METH_VARARGS | METH_KEYWORDS, NULL},
+    {"search", (PyCFunction) BinarySearchTree_search, METH_VARARGS | METH_KEYWORDS, NULL},
+    {"lower_bound", (PyCFunction) BinarySearchTree_lower_bound, METH_VARARGS | METH_KEYWORDS, NULL},
+    {"upper_bound", (PyCFunction) BinarySearchTree_upper_bound, METH_VARARGS | METH_KEYWORDS, NULL},
+    {"_simple_path", (PyCFunction) BinarySearchTree__simple_path, METH_VARARGS, NULL},
+    {"_lca_1", (PyCFunction) BinarySearchTree__lca_1, METH_VARARGS, NULL},
+    {"_lca_2", (PyCFunction) BinarySearchTree__lca_2, METH_VARARGS, NULL},
+    {"lowest_common_ancestor", (PyCFunction) BinarySearchTree_lowest_common_ancestor, METH_VARARGS, NULL},
+    {"rank", (PyCFunction) BinarySearchTree_rank, METH_VARARGS, NULL},
+    {"select", (PyCFunction) BinarySearchTree_select, METH_VARARGS, NULL},
+    {NULL}
+};
+
+static PyMemberDef BinarySearchTree_PyMemberDef[] = {
+    {"tree", T_OBJECT_EX, offsetof(BinarySearchTree, tree), 0, "tree"},
+    {NULL}  /* Sentinel */
+};
+
+
+static PyTypeObject BinarySearchTreeType = {
+    /* tp_name */ PyVarObject_HEAD_INIT(NULL, 0) "BinarySearchTree",
+    /* tp_basicsize */ sizeof(BinarySearchTree),
+    /* tp_itemsize */ 0,
+    /* tp_dealloc */ (destructor) BinarySearchTree_dealloc,
+    /* tp_print */ 0,
+    /* tp_getattr */ 0,
+    /* tp_setattr */ 0,
+    /* tp_reserved */ 0,
+    /* tp_repr */ 0,
+    /* tp_as_number */ 0,
+    /* tp_as_sequence */ 0,
+    /* tp_as_mapping */ 0,
+    /* tp_hash  */ 0,
+    /* tp_call */ 0,
+    /* tp_str */ (reprfunc) BinarySearchTree___str__,
+    /* tp_getattro */ 0,
+    /* tp_setattro */ 0,
+    /* tp_as_buffer */ 0,
+    /* tp_flags */ Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE,
+    /* tp_doc */ 0,
+    /* tp_traverse */ 0,
+    /* tp_clear */ 0,
+    /* tp_richcompare */ 0,
+    /* tp_weaklistoffset */ 0,
+    /* tp_iter */ 0,
+    /* tp_iternext */ 0,
+    /* tp_methods */ BinarySearchTree_PyMethodDef,
+    /* tp_members */ BinarySearchTree_PyMemberDef,
+    /* tp_getset */ 0,
+    /* tp_base */ &BinaryTreeType,
+    /* tp_dict */ 0,
+    /* tp_descr_get */ 0,
+    /* tp_descr_set */ 0,
+    /* tp_dictoffset */ 0,
+    /* tp_init */ 0,
+    /* tp_alloc */ 0,
+    /* tp_new */ BinarySearchTree___new__,
+};
+
+#endif
diff --git a/pydatastructs/trees/_backend/cpp/BinaryTree.hpp b/pydatastructs/trees/_backend/cpp/BinaryTree.hpp
new file mode 100644
index 000000000..f07eab4a8
--- /dev/null
+++ b/pydatastructs/trees/_backend/cpp/BinaryTree.hpp
@@ -0,0 +1,174 @@
+#ifndef TREES_BINARYTREE_HPP
+#define TREES_BINARYTREE_HPP
+
+#define PY_SSIZE_T_CLEAN
+#include <Python.h>
+#include <structmember.h>
+#include <cstdlib>
+#include "../../../utils/_backend/cpp/utils.hpp"
+#include "../../../utils/_backend/cpp/TreeNode.hpp"
+#include "../../../linear_data_structures/_backend/cpp/arrays/ArrayForTrees.hpp"
+#include "../../../linear_data_structures/_backend/cpp/arrays/DynamicOneDimensionalArray.hpp"
+
+typedef struct {
+    PyObject_HEAD
+    ArrayForTrees* tree;
+    PyObject* root_idx;
+    PyObject* comparator;
+    long size;
+    long is_order_statistic;
+} BinaryTree;
+
+static void BinaryTree_dealloc(BinaryTree *self) {
+    Py_TYPE(self)->tp_free(reinterpret_cast<PyObject*>(self));
+}
+
+static PyObject* BinaryTree___new__(PyTypeObject* type, PyObject *args, PyObject *kwds) {
+    BinaryTree *self;
+    self = reinterpret_cast<BinaryTree*>(type->tp_alloc(type, 0));
+
+    // Assume that arguments are in the order below. Modify the python code such that this is true (ie; pass None for other arguments)
+    PyObject *key = PyObject_GetItem(args, PyZero);
+    PyObject *root_data = PyObject_GetItem(args, PyOne);
+    PyObject *comp = PyObject_GetItem(args, PyTwo);
+    PyObject *is_order_statistic = PyObject_GetItem(args, PyThree);
+    if ( (key == Py_None) && (root_data != Py_None) ) {
+        PyErr_SetString(PyExc_ValueError, "Key required.");
+        return NULL;
+    }
+    Py_INCREF(Py_None);
+    key = root_data == Py_None ? Py_None : key;
+
+    if (PyType_Ready(&TreeNodeType) < 0) { // This has to be present to finalize a type object. This should be called on all type objects to finish their initialization.
+        return NULL;
+    }
+    TreeNode* root = reinterpret_cast<TreeNode*>(TreeNode___new__(&TreeNodeType, args, kwds));
+    root->is_root = true;
+    self->root_idx = PyLong_FromLong(0);
+
+    PyObject* listroot = Py_BuildValue("[O]", root);
+    if (PyType_Ready(&ArrayForTreesType) < 0) { // This has to be present to finalize a type object. This should be called on all type objects to finish their initialization.
+        return NULL;
+    }
+    if (PyType_Ready(&DynamicOneDimensionalArrayType) < 0) { // This has to be present to finalize a type object. This should be called on all type objects to finish their initialization.
+        return NULL;
+    }
+    if (PyType_Ready(&TreeNodeType) < 0) { // This has to be present to finalize a type object. This should be called on all type objects to finish their initialization.
+        return NULL;
+    }
+
+    Py_INCREF(Py_None);
+    PyObject* args2 = Py_BuildValue("(OO)", &TreeNodeType, listroot);
+    PyObject* kwds2 = Py_BuildValue("()");
+    if (PyType_Ready(&DynamicOneDimensionalArrayType) < 0) { // This has to be present to finalize a type object. This should be called on all type objects to finish their initialization.
+        return NULL;
+    }
+    ArrayForTrees* arr = reinterpret_cast<ArrayForTrees*>(ArrayForTrees___new__(&ArrayForTreesType, args2, kwds2));
+    if ( !arr ) {
+        return NULL;
+    }
+    self->tree = arr;
+    self->size = 1;
+    // Python code is modified to ensure comp is never None
+    if (!PyCallable_Check(comp)) {
+            PyErr_SetString(PyExc_ValueError, "comparator should be callable");
+            return NULL;
+    }
+    self->comparator = comp;
+    self->is_order_statistic = PyLong_AsLong(is_order_statistic);
+
+    return reinterpret_cast<PyObject*>(self);
+}
+
+static PyObject* BinaryTree_insert(PyTypeObject* type, PyObject *args, PyObject *kwds) {
+    PyErr_SetString(PyExc_NotImplementedError, "This is an abstract method.");
+    return NULL;
+}
+
+static PyObject* BinaryTree_delete(PyTypeObject* type, PyObject *args, PyObject *kwds) {
+    PyErr_SetString(PyExc_NotImplementedError, "This is an abstract method.");
+    return NULL;
+}
+
+static PyObject* BinaryTree_search(PyTypeObject* type, PyObject *args, PyObject *kwds) {
+    PyErr_SetString(PyExc_NotImplementedError, "This is an abstract method.");
+    return NULL;
+}
+
+static PyObject* BinaryTree___str__(BinaryTree *self) {
+    long size = self->tree->_last_pos_filled + 1;
+    PyObject* list = PyList_New(size);
+    for(int i=0;i<size;i++) {
+        OneDimensionalArray* oda = self->tree->_one_dimensional_array;
+        TreeNode* node = reinterpret_cast<TreeNode*>(oda->_data[i]);
+        if (reinterpret_cast<PyObject*>(node) != Py_None) {
+            PyObject* out = Py_BuildValue("(OOOO)", node->left, node->key, node->data, node->right);
+            Py_INCREF(out);
+            PyList_SET_ITEM(list, i, out);
+        }
+        else {
+            PyObject* empty_string = PyUnicode_FromString("");
+            PyList_SET_ITEM(list, i, empty_string);
+        }
+    }
+    return PyObject_Str(list);
+}
+
+static struct PyMethodDef BinaryTree_PyMethodDef[] = {
+    {"insert", (PyCFunction) BinaryTree_insert, METH_VARARGS | METH_KEYWORDS, NULL},
+    {"delete", (PyCFunction) BinaryTree_delete, METH_VARARGS | METH_KEYWORDS, NULL},
+    {"search", (PyCFunction) BinaryTree_search, METH_VARARGS | METH_KEYWORDS, NULL},
+    {NULL}
+};
+
+static PyMemberDef BinaryTree_PyMemberDef[] = {
+    {"root_idx", T_OBJECT, offsetof(BinaryTree, root_idx), READONLY, "Index of the root node"},
+    {"comparator", T_OBJECT, offsetof(BinaryTree, comparator), 0, "Comparator function"},
+    {"tree", T_OBJECT_EX, offsetof(BinaryTree, tree), 0, "Tree"},
+    {"size", T_LONG, offsetof(BinaryTree, size), READONLY, "Size of the tree"},
+    {"is_order_statistic", T_LONG, offsetof(BinaryTree, is_order_statistic), 0, "Whether the tree is ordered statically or not"},
+    {NULL}  /* Sentinel */
+};
+
+
+static PyTypeObject BinaryTreeType = {
+    /* tp_name */ PyVarObject_HEAD_INIT(NULL, 0) "BinaryTree",
+    /* tp_basicsize */ sizeof(BinaryTree),
+    /* tp_itemsize */ 0,
+    /* tp_dealloc */ (destructor) BinaryTree_dealloc,
+    /* tp_print */ 0,
+    /* tp_getattr */ 0,
+    /* tp_setattr */ 0,
+    /* tp_reserved */ 0,
+    /* tp_repr */ 0,
+    /* tp_as_number */ 0,
+    /* tp_as_sequence */ 0,
+    /* tp_as_mapping */ 0,
+    /* tp_hash  */ 0,
+    /* tp_call */ 0,
+    /* tp_str */ (reprfunc) BinaryTree___str__,
+    /* tp_getattro */ 0,
+    /* tp_setattro */ 0,
+    /* tp_as_buffer */ 0,
+    /* tp_flags */ Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE,
+    /* tp_doc */ 0,
+    /* tp_traverse */ 0,
+    /* tp_clear */ 0,
+    /* tp_richcompare */ 0,
+    /* tp_weaklistoffset */ 0,
+    /* tp_iter */ 0,
+    /* tp_iternext */ 0,
+    /* tp_methods */ BinaryTree_PyMethodDef,
+    /* tp_members */ BinaryTree_PyMemberDef,
+    /* tp_getset */ 0,
+    /* tp_base */ &PyBaseObject_Type,
+    /* tp_dict */ 0,
+    /* tp_descr_get */ 0,
+    /* tp_descr_set */ 0,
+    /* tp_dictoffset */ 0,
+    /* tp_init */ 0,
+    /* tp_alloc */ 0,
+    /* tp_new */ BinaryTree___new__,
+};
+
+#endif
diff --git a/pydatastructs/trees/_backend/cpp/BinaryTreeTraversal.hpp b/pydatastructs/trees/_backend/cpp/BinaryTreeTraversal.hpp
new file mode 100644
index 000000000..a20e6b5aa
--- /dev/null
+++ b/pydatastructs/trees/_backend/cpp/BinaryTreeTraversal.hpp
@@ -0,0 +1,255 @@
+#ifndef TREES_BINARYTREETRAVERSAL_HPP
+#define TREES_BINARYTREETRAVERSAL_HPP
+
+#define PY_SSIZE_T_CLEAN
+#include <Python.h>
+#include <structmember.h>
+#include <cstdlib>
+#include <stack>
+#include <queue>
+#include <string>
+#include "../../../utils/_backend/cpp/utils.hpp"
+#include "../../../utils/_backend/cpp/TreeNode.hpp"
+#include "../../../linear_data_structures/_backend/cpp/arrays/ArrayForTrees.hpp"
+#include "BinaryTree.hpp"
+#include "BinarySearchTree.hpp"
+
+typedef struct {
+    PyObject_HEAD
+    BinaryTree* tree;
+} BinaryTreeTraversal;
+
+static void BinaryTreeTraversal_dealloc(BinaryTreeTraversal *self) {
+    BinaryTree_dealloc(self->tree);
+    Py_TYPE(self)->tp_free(reinterpret_cast<PyObject*>(self));
+}
+
+static PyObject* BinaryTreeTraversal___new__(PyTypeObject* type, PyObject *args, PyObject *kwds) {
+    BinaryTreeTraversal *self;
+    self = reinterpret_cast<BinaryTreeTraversal*>(type->tp_alloc(type, 0));
+
+    PyObject* tree = PyObject_GetItem(args, PyZero);
+    if (PyType_Ready(&BinarySearchTreeType) < 0) { // This has to be present to finalize a type object. This should be called on all type objects to finish their initialization.
+        return NULL;
+    }
+    if (PyObject_IsInstance(tree, (PyObject *)&BinarySearchTreeType)) {
+        self->tree = reinterpret_cast<BinarySearchTree*>(tree)->binary_tree;
+    }
+    else {
+        PyErr_SetString(PyExc_ValueError, "Not a supported type for BinaryTreeTraversal.");
+        return NULL;
+    }
+    return reinterpret_cast<PyObject*>(self);
+}
+
+static PyObject* BinaryTreeTraversal__pre_order(BinaryTreeTraversal* self, PyObject *args) {
+    long node = PyLong_AsLong(PyObject_GetItem(args, PyZero));
+    PyObject* visit = PyList_New(0);
+    ArrayForTrees* tree = self->tree->tree;
+    long size = self->tree->size;
+    std::stack<long> s;
+    s.push(node);
+
+    while (!s.empty()) {
+        node = s.top();
+        s.pop();
+        TreeNode* curr_node = reinterpret_cast<TreeNode*>(tree->_one_dimensional_array->_data[node]);
+        PyList_Append(visit, reinterpret_cast<PyObject*>(curr_node));
+        if (curr_node->right != Py_None) {
+            s.push(PyLong_AsLong(curr_node->right));
+        }
+        if (curr_node->left != Py_None) {
+            s.push(PyLong_AsLong(curr_node->left));
+        }
+    }
+    return visit;
+}
+
+static PyObject* BinaryTreeTraversal__in_order(BinaryTreeTraversal* self, PyObject *args) {
+    PyObject* node = PyObject_GetItem(args, PyZero);
+    PyObject* visit = PyList_New(0);
+    ArrayForTrees* tree = self->tree->tree;
+    long size = self->tree->size;
+    std::stack<PyObject*> s;
+
+    while (!s.empty() || node != Py_None) {
+        if (node != Py_None) {
+            s.push(node);
+            node = reinterpret_cast<TreeNode*>(tree->_one_dimensional_array->_data[PyLong_AsLong(node)])->left;
+        }
+        else {
+            node = s.top();
+            s.pop();
+            TreeNode* curr_node = reinterpret_cast<TreeNode*>(tree->_one_dimensional_array->_data[PyLong_AsLong(node)]);
+            PyList_Append(visit, reinterpret_cast<PyObject*>(curr_node));
+            node = curr_node->right;
+        }
+    }
+    return visit;
+}
+
+static PyObject* BinaryTreeTraversal__post_order(BinaryTreeTraversal* self, PyObject *args) {
+    PyObject* node = PyObject_GetItem(args, PyZero);
+    PyObject* visit = PyList_New(0);
+    ArrayForTrees* tree = self->tree->tree;
+    long size = self->tree->size;
+    std::stack<PyObject*> s;
+    s.push(node);
+    PyObject* last = PyList_New(size);
+    for (int i=0;i<size;i++) {
+        PyList_SetItem(last, i, PyZero);
+    }
+
+    while (!s.empty()) {
+        PyObject* node = s.top();
+        PyObject* l = reinterpret_cast<TreeNode*>(tree->_one_dimensional_array->_data[PyLong_AsLong(node)])->left;
+        PyObject* r = reinterpret_cast<TreeNode*>(tree->_one_dimensional_array->_data[PyLong_AsLong(node)])->right;
+        bool cl = false, cr = false;
+        if (l == Py_None || PyList_GetItem(last, PyLong_AsLong(l)) == PyOne) {
+            cl = true;
+        }
+        if (r == Py_None || PyList_GetItem(last, PyLong_AsLong(r)) == PyOne) {
+            cr = true;
+        }
+        if (cl && cr) {
+            s.pop();
+            TreeNode* curr_node = reinterpret_cast<TreeNode*>(tree->_one_dimensional_array->_data[PyLong_AsLong(node)]);
+            PyList_Append(visit, reinterpret_cast<PyObject*>(curr_node));
+            PyList_SetItem(last, PyLong_AsLong(node), PyOne);
+            continue;
+        }
+        if (!cr) {
+            s.push(r);
+        }
+        if (!cl) {
+            s.push(l);
+        }
+    }
+    return visit;
+}
+
+static PyObject* BinaryTreeTraversal__out_order(BinaryTreeTraversal* self, PyObject *args) {
+    PyObject* node = PyObject_GetItem(args, PyZero);
+    PyObject* visit = BinaryTreeTraversal__in_order(self, Py_BuildValue("(O)", node));
+    PyList_Reverse(visit);
+    return visit;
+}
+
+static PyObject* BinaryTreeTraversal_depth_first_search(BinaryTreeTraversal* self, PyObject *args, PyObject *kwds) {
+    Py_INCREF(Py_None);
+    PyObject* node = Py_None;
+    PyObject* order = PyUnicode_FromString("in_order");
+    static char* keywords[] = {"node","order", NULL};
+    if (!PyArg_ParseTupleAndKeywords(args, kwds, "|OO", keywords, &node, &order)) {
+        return NULL;
+    }
+    if (node == Py_None) {
+        node = self->tree->root_idx;
+    }
+    if (PyUnicode_Compare(order, PyUnicode_FromString("pre_order")) == 0) {
+        return BinaryTreeTraversal__pre_order(self, Py_BuildValue("(O)", node));
+    }
+    else if (PyUnicode_Compare(order, PyUnicode_FromString("in_order")) == 0) {
+        return BinaryTreeTraversal__in_order(self, Py_BuildValue("(O)", node));
+    }
+    else if (PyUnicode_Compare(order, PyUnicode_FromString("out_order")) == 0) {
+        return BinaryTreeTraversal__out_order(self, Py_BuildValue("(O)", node));
+    }
+    else if (PyUnicode_Compare(order, PyUnicode_FromString("post_order")) == 0) {
+        return BinaryTreeTraversal__post_order(self, Py_BuildValue("(O)", node));
+    }
+    else {
+        PyErr_SetString(PyExc_NotImplementedError, "This traversal is not implemented yet or does not exist. Supported traversals: \"pre_order\", \"in_order\", \"out_order\", , \"post_order\"");
+        return NULL;
+    }
+}
+
+static PyObject* BinaryTreeTraversal_breadth_first_search(BinaryTreeTraversal* self, PyObject *args, PyObject *kwds) {
+    Py_INCREF(Py_None);
+    PyObject* node = Py_None;
+    PyObject* strategy = PyUnicode_FromString("queue");
+    static char* keywords[] = {"node","strategy", NULL};
+    if (!PyArg_ParseTupleAndKeywords(args, kwds, "|OO", keywords, &node, &strategy)) {
+        return NULL;
+    }
+    if (PyUnicode_Compare(strategy, PyUnicode_FromString("queue")) == 0) {
+        if (node == Py_None) {
+            node = self->tree->root_idx;
+        }
+        std::queue<PyObject*> q;
+        PyObject* visit = PyList_New(0);
+        ArrayForTrees* tree = self->tree->tree;
+        q.push(node);
+        while (q.size() > 0) {
+            node = q.front();
+            q.pop();
+            TreeNode* curr_node = reinterpret_cast<TreeNode*>(tree->_one_dimensional_array->_data[PyLong_AsLong(node)]);
+            PyList_Append(visit, reinterpret_cast<PyObject*>(curr_node));
+            if (curr_node->left != Py_None) {
+                q.push(curr_node->left);
+            }
+            if (curr_node->right != Py_None) {
+                q.push(curr_node->right);
+            }
+        }
+
+        return visit;
+    }
+    else {
+        PyErr_SetString(PyExc_NotImplementedError, "This strategy has not been implemented yet.");
+        return NULL;
+    }
+}
+
+static struct PyMethodDef BinaryTreeTraversal_PyMethodDef[] = {
+    {"_pre_order", (PyCFunction) BinaryTreeTraversal__pre_order, METH_VARARGS, NULL},
+    {"_in_order", (PyCFunction) BinaryTreeTraversal__in_order, METH_VARARGS, NULL},
+    {"_out_order", (PyCFunction) BinaryTreeTraversal__out_order, METH_VARARGS, NULL},
+    {"_post_order", (PyCFunction) BinaryTreeTraversal__post_order, METH_VARARGS, NULL},
+    {"depth_first_search", (PyCFunction) BinaryTreeTraversal_depth_first_search, METH_VARARGS | METH_KEYWORDS, NULL},
+    {"breadth_first_search", (PyCFunction) BinaryTreeTraversal_breadth_first_search, METH_VARARGS | METH_KEYWORDS, NULL},
+    {NULL}
+};
+
+
+static PyTypeObject BinaryTreeTraversalType = {
+    /* tp_name */ PyVarObject_HEAD_INIT(NULL, 0) "BinaryTreeTraversal",
+    /* tp_basicsize */ sizeof(BinaryTreeTraversal),
+    /* tp_itemsize */ 0,
+    /* tp_dealloc */ (destructor) BinaryTreeTraversal_dealloc,
+    /* tp_print */ 0,
+    /* tp_getattr */ 0,
+    /* tp_setattr */ 0,
+    /* tp_reserved */ 0,
+    /* tp_repr */ 0,
+    /* tp_as_number */ 0,
+    /* tp_as_sequence */ 0,
+    /* tp_as_mapping */ 0,
+    /* tp_hash  */ 0,
+    /* tp_call */ 0,
+    /* tp_str */ 0,
+    /* tp_getattro */ 0,
+    /* tp_setattro */ 0,
+    /* tp_as_buffer */ 0,
+    /* tp_flags */ Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE,
+    /* tp_doc */ 0,
+    /* tp_traverse */ 0,
+    /* tp_clear */ 0,
+    /* tp_richcompare */ 0,
+    /* tp_weaklistoffset */ 0,
+    /* tp_iter */ 0,
+    /* tp_iternext */ 0,
+    /* tp_methods */ BinaryTreeTraversal_PyMethodDef,
+    /* tp_members */ 0,
+    /* tp_getset */ 0,
+    /* tp_base */ &PyBaseObject_Type,
+    /* tp_dict */ 0,
+    /* tp_descr_get */ 0,
+    /* tp_descr_set */ 0,
+    /* tp_dictoffset */ 0,
+    /* tp_init */ 0,
+    /* tp_alloc */ 0,
+    /* tp_new */ BinaryTreeTraversal___new__,
+};
+
+#endif
diff --git a/pydatastructs/trees/_backend/cpp/trees.cpp b/pydatastructs/trees/_backend/cpp/trees.cpp
new file mode 100644
index 000000000..89699d008
--- /dev/null
+++ b/pydatastructs/trees/_backend/cpp/trees.cpp
@@ -0,0 +1,37 @@
+#include <Python.h>
+#include "BinaryTree.hpp"
+#include "BinarySearchTree.hpp"
+#include "BinaryTreeTraversal.hpp"
+
+static struct PyModuleDef trees_struct = {
+    PyModuleDef_HEAD_INIT,
+    "_trees",
+    0,
+    -1,
+    NULL,
+};
+
+PyMODINIT_FUNC PyInit__trees(void) {
+    Py_Initialize();
+    PyObject *trees = PyModule_Create(&trees_struct);
+
+    if (PyType_Ready(&BinaryTreeType) < 0) {
+        return NULL;
+    }
+    Py_INCREF(&BinaryTreeType);
+    PyModule_AddObject(trees, "BinaryTree", reinterpret_cast<PyObject*>(&BinaryTreeType));
+
+    if (PyType_Ready(&BinarySearchTreeType) < 0) {
+        return NULL;
+    }
+    Py_INCREF(&BinarySearchTreeType);
+    PyModule_AddObject(trees, "BinarySearchTree", reinterpret_cast<PyObject*>(&BinarySearchTreeType));
+
+    if (PyType_Ready(&BinaryTreeTraversalType) < 0) {
+        return NULL;
+    }
+    Py_INCREF(&BinaryTreeTraversalType);
+    PyModule_AddObject(trees, "BinaryTreeTraversal", reinterpret_cast<PyObject*>(&BinaryTreeTraversalType));
+
+    return trees;
+}
diff --git a/pydatastructs/trees/_extensions.py b/pydatastructs/trees/_extensions.py
new file mode 100644
index 000000000..214e1d8a5
--- /dev/null
+++ b/pydatastructs/trees/_extensions.py
@@ -0,0 +1,17 @@
+from setuptools import Extension
+
+project = 'pydatastructs'
+
+module = 'trees'
+
+backend = '_backend'
+
+cpp = 'cpp'
+
+trees = '.'.join([project, module, backend, cpp, '_trees'])
+trees_sources = ['/'.join([project, module, backend, cpp,
+                            'trees.cpp'])]
+
+extensions = [
+    Extension(trees, sources=trees_sources)
+]
diff --git a/pydatastructs/trees/binary_trees.py b/pydatastructs/trees/binary_trees.py
index 8a39c5213..27addf595 100644
--- a/pydatastructs/trees/binary_trees.py
+++ b/pydatastructs/trees/binary_trees.py
@@ -6,6 +6,7 @@
 from pydatastructs.linear_data_structures.arrays import ArrayForTrees
 from pydatastructs.utils.misc_util import (
     Backend, raise_if_backend_is_not_python)
+from pydatastructs.trees._backend.cpp import _trees
 
 __all__ = [
     'AVLTree',
@@ -58,8 +59,11 @@ class BinaryTree(object):
 
     def __new__(cls, key=None, root_data=None, comp=None,
                 is_order_statistic=False, **kwargs):
-        raise_if_backend_is_not_python(
-            cls, kwargs.get('backend', Backend.PYTHON))
+        backend = kwargs.get('backend', Backend.PYTHON)
+        if backend == Backend.CPP:
+            if comp is None:
+                comp = lambda key1, key2: key1 < key2
+            return _trees.BinaryTree(key, root_data, comp, is_order_statistic, **kwargs) # If any argument is not given, then it is passed as None, except for comp
         obj = object.__new__(cls)
         if key is None and root_data is not None:
             raise ValueError('Key required.')
@@ -219,6 +223,14 @@ def methods(cls):
                                         if node.left is not None else 0
     right_size = lambda self, node: self.tree[node.right].size \
                                         if node.right is not None else 0
+    def __new__(cls, key=None, root_data=None, comp=None,
+                is_order_statistic=False, **kwargs):
+        backend = kwargs.get('backend', Backend.PYTHON)
+        if backend == Backend.CPP:
+            if comp is None:
+                comp = lambda key1, key2: key1 < key2
+            return _trees.BinarySearchTree(key, root_data, comp, is_order_statistic, **kwargs) # If any argument is not given, then it is passed as None, except for comp
+        return super().__new__(cls, key, root_data, comp, is_order_statistic, **kwargs)
 
     def _update_size(self, start_idx):
         if self.is_order_statistic:
@@ -612,7 +624,6 @@ def _lca_2(self, j, k):
                 if curr_root is None:
                     return None
                 return self.tree[curr_root].key
-
             u_left = self.comparator(self.tree[u].key, \
                 self.tree[curr_root].key)
             v_left = self.comparator(self.tree[v].key, \
@@ -1547,8 +1558,9 @@ def methods(cls):
     __slots__ = ['tree']
 
     def __new__(cls, tree, **kwargs):
-        raise_if_backend_is_not_python(
-            cls, kwargs.get('backend', Backend.PYTHON))
+        backend = kwargs.get('backend', Backend.PYTHON)
+        if backend == Backend.CPP:
+            return _trees.BinaryTreeTraversal(tree, **kwargs)
         if not isinstance(tree, BinaryTree):
             raise TypeError("%s is not a binary tree"%(tree))
         obj = object.__new__(cls)
diff --git a/pydatastructs/utils/__init__.py b/pydatastructs/utils/__init__.py
index 707f28791..20a8c750c 100644
--- a/pydatastructs/utils/__init__.py
+++ b/pydatastructs/utils/__init__.py
@@ -1,7 +1,11 @@
 __all__ = []
 
-from . import misc_util
-from . import testing_util
+from . import (
+    misc_util,
+    testing_util,
+    _extensions
+)
+
 from .misc_util import (
     TreeNode,
     MAryTreeNode,
diff --git a/pydatastructs/utils/_backend/cpp/Node.hpp b/pydatastructs/utils/_backend/cpp/Node.hpp
new file mode 100644
index 000000000..c18d708a2
--- /dev/null
+++ b/pydatastructs/utils/_backend/cpp/Node.hpp
@@ -0,0 +1,59 @@
+#ifndef UTILS_NODE_HPP
+#define UTILS_NODE_HPP
+
+#define PY_SSIZE_T_CLEAN
+#include <Python.h>
+#include <structmember.h>
+#include "utils.hpp"
+
+typedef struct {
+    PyObject_HEAD
+} Node;
+// Node is an abstract class representing a Node
+
+static void Node_dealloc(Node *self) {
+    Py_TYPE(self)->tp_free(reinterpret_cast<PyObject*>(self));
+}
+
+
+static PyTypeObject NodeType = {
+    /* tp_name */ PyVarObject_HEAD_INIT(NULL, 0) "Node",
+    /* tp_basicsize */ sizeof(Node),
+    /* tp_itemsize */ 0,
+    /* tp_dealloc */ (destructor) Node_dealloc,
+    /* tp_print */ 0,
+    /* tp_getattr */ 0,
+    /* tp_setattr */ 0,
+    /* tp_reserved */ 0,
+    /* tp_repr */ 0,
+    /* tp_as_number */ 0,
+    /* tp_as_sequence */ 0,
+    /* tp_as_mapping */ 0,
+    /* tp_hash  */ 0,
+    /* tp_call */ 0,
+    /* tp_str */ 0,
+    /* tp_getattro */ 0,
+    /* tp_setattro */ 0,
+    /* tp_as_buffer */ 0,
+    /* tp_flags */ Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE,
+    /* tp_doc */ 0,
+    /* tp_traverse */ 0,
+    /* tp_clear */ 0,
+    /* tp_richcompare */ 0,
+    /* tp_weaklistoffset */ 0,
+    /* tp_iter */ 0,
+    /* tp_iternext */ 0,
+    /* tp_methods */ 0,
+    /* tp_members */ 0,
+    /* tp_getset */ 0,
+    /* tp_base */ &PyBaseObject_Type,
+    /* tp_dict */ 0,
+    /* tp_descr_get */ 0,
+    /* tp_descr_set */ 0,
+    /* tp_dictoffset */ 0,
+    /* tp_init */ 0,
+    /* tp_alloc */ 0,
+    /* tp_new */ 0,
+};
+
+#endif
diff --git a/pydatastructs/utils/_backend/cpp/TreeNode.hpp b/pydatastructs/utils/_backend/cpp/TreeNode.hpp
new file mode 100644
index 000000000..41c64f724
--- /dev/null
+++ b/pydatastructs/utils/_backend/cpp/TreeNode.hpp
@@ -0,0 +1,106 @@
+#ifndef UTILS_TREENODE_HPP
+#define UTILS_TREENODE_HPP
+
+#define PY_SSIZE_T_CLEAN
+#include <Python.h>
+#include <structmember.h>
+#include "Node.hpp"
+#include "utils.hpp"
+
+typedef struct {
+    PyObject_HEAD
+    PyObject* key;
+    PyObject* data; // can store None or a number
+    PyObject* left; // can store None or a number
+    PyObject* right; // can store None or a number
+    bool is_root;
+    long height;
+    PyObject* parent;
+    long size;
+} TreeNode;
+
+static void TreeNode_dealloc(TreeNode *self) {
+    Py_TYPE(self)->tp_free(reinterpret_cast<PyObject*>(self));
+}
+
+static PyObject* TreeNode___new__(PyTypeObject* type, PyObject *args, PyObject *kwds) {
+    TreeNode *self;
+    self = reinterpret_cast<TreeNode*>(type->tp_alloc(type, 0));
+
+    // Assume that arguments are in the order below. Python code is such that this is true.
+    self->key = PyObject_GetItem(args, PyZero);
+    self->data = PyObject_GetItem(args, PyOne);
+
+    Py_INCREF(Py_None);
+    self->left = Py_None;
+    Py_INCREF(Py_None);
+    self->right = Py_None;
+    Py_INCREF(Py_None);
+    self->parent = Py_None;
+    self->height = 0;
+    self->size = 1;
+    self->is_root = false;
+
+    return reinterpret_cast<PyObject*>(self);
+}
+
+static PyObject* TreeNode___str__(TreeNode *self) {
+    PyObject* out = Py_BuildValue("(OOOO)", self->left, self->key, self->data, self->right);
+    Py_INCREF(out);
+    return PyObject_Str(out);
+}
+
+static struct PyMemberDef TreeNode_PyMemberDef[] = {
+    {"key", T_OBJECT, offsetof(TreeNode, key), 0, "TreeNode key"},
+    {"data", T_OBJECT, offsetof(TreeNode, data), 0, "TreeNode data"},
+    {"height", T_LONG, offsetof(TreeNode, height), 0, "TreeNode height"},
+    {"size", T_LONG, offsetof(TreeNode, size), 0, "TreeNode size"},
+    {"is_root", T_BOOL, offsetof(TreeNode, is_root), 0, "TreeNode is_root"},
+    {"left", T_OBJECT, offsetof(TreeNode, left), 0, "TreeNode left"},
+    {"right", T_OBJECT, offsetof(TreeNode, right), 0, "TreeNode right"},
+    {"parent", T_OBJECT, offsetof(TreeNode, parent), 0, "TreeNode parent"},
+    {NULL},
+};
+
+
+static PyTypeObject TreeNodeType = {
+    /* tp_name */ PyVarObject_HEAD_INIT(NULL, 0) "TreeNode",
+    /* tp_basicsize */ sizeof(TreeNode),
+    /* tp_itemsize */ 0,
+    /* tp_dealloc */ (destructor) TreeNode_dealloc,
+    /* tp_print */ 0,
+    /* tp_getattr */ 0,
+    /* tp_setattr */ 0,
+    /* tp_reserved */ 0,
+    /* tp_repr */ 0,
+    /* tp_as_number */ 0,
+    /* tp_as_sequence */ 0,
+    /* tp_as_mapping */ 0,
+    /* tp_hash  */ 0,
+    /* tp_call */ 0,
+    /* tp_str */ (reprfunc) TreeNode___str__,
+    /* tp_getattro */ 0,
+    /* tp_setattro */ 0,
+    /* tp_as_buffer */ 0,
+    /* tp_flags */ Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE,
+    /* tp_doc */ 0,
+    /* tp_traverse */ 0,
+    /* tp_clear */ 0,
+    /* tp_richcompare */ 0,
+    /* tp_weaklistoffset */ 0,
+    /* tp_iter */ 0,
+    /* tp_iternext */ 0,
+    /* tp_methods */ 0,
+    /* tp_members */ TreeNode_PyMemberDef,
+    /* tp_getset */ 0,
+    /* tp_base */ &NodeType, // Class Node is the base class
+    /* tp_dict */ 0,
+    /* tp_descr_get */ 0,
+    /* tp_descr_set */ 0,
+    /* tp_dictoffset */ 0,
+    /* tp_init */ 0,
+    /* tp_alloc */ 0,
+    /* tp_new */ TreeNode___new__,
+};
+
+#endif
diff --git a/pydatastructs/utils/_backend/cpp/nodes.cpp b/pydatastructs/utils/_backend/cpp/nodes.cpp
new file mode 100644
index 000000000..4e50d6966
--- /dev/null
+++ b/pydatastructs/utils/_backend/cpp/nodes.cpp
@@ -0,0 +1,30 @@
+#include <Python.h>
+#include "Node.hpp"
+#include "TreeNode.hpp"
+
+static struct PyModuleDef nodes_struct = {
+    PyModuleDef_HEAD_INIT,
+    "_nodes",
+    0,
+    -1,
+    NULL,
+};
+
+PyMODINIT_FUNC PyInit__nodes(void) {
+    Py_Initialize();
+    PyObject *nodes = PyModule_Create(&nodes_struct);
+
+    if (PyType_Ready(&NodeType) < 0) {
+        return NULL;
+    }
+    Py_INCREF(&NodeType);
+    PyModule_AddObject(nodes, "Node", reinterpret_cast<PyObject*>(&NodeType));
+
+    if (PyType_Ready(&TreeNodeType) < 0) {
+        return NULL;
+    }
+    Py_INCREF(&TreeNodeType);
+    PyModule_AddObject(nodes, "TreeNode", reinterpret_cast<PyObject*>(&TreeNodeType));
+
+    return nodes;
+}
diff --git a/pydatastructs/utils/_backend/cpp/utils.hpp b/pydatastructs/utils/_backend/cpp/utils.hpp
index e0b1337be..33cc05fc0 100644
--- a/pydatastructs/utils/_backend/cpp/utils.hpp
+++ b/pydatastructs/utils/_backend/cpp/utils.hpp
@@ -9,6 +9,7 @@
 PyObject *PyZero = PyLong_FromLong(0);
 PyObject *PyOne = PyLong_FromLong(1);
 PyObject *PyTwo = PyLong_FromLong(2);
+PyObject *PyThree = PyLong_FromLong(3);
 const char* _encoding = "utf-8";
 const char* _invalid_char = "<invalid-character>";
 
@@ -20,14 +21,14 @@ static PyObject* __str__(PyObject** array, size_t size, long last_pos_filled=-1)
     std::string array___str__ = "[";
     size_t end = last_pos_filled == -1 ? size : (size_t) (last_pos_filled + 1);
     for( size_t i = 0; i < end; i++ ) {
-        if( array[i] == Py_None ) {
+        if ( array[i] == Py_None ) {
             array___str__.append("''");
         } else {
             PyObject* array_i = PyObject_Str(array[i]);
             char* i___str__ = PyObject_AsString(array_i);
             array___str__.append("'" + std::string(i___str__) + "'");
         }
-        if( i + 1 != end ) {
+        if ( i + 1 != end ) {
             array___str__.append(", ");
         }
     }
@@ -36,7 +37,7 @@ static PyObject* __str__(PyObject** array, size_t size, long last_pos_filled=-1)
 }
 
 static int set_exception_if_dtype_mismatch(PyObject* value, PyObject* dtype) {
-    if( !PyObject_IsInstance(value, dtype) ) {
+    if ( !PyObject_IsInstance(value, dtype) ) {
         PyErr_WriteUnraisable(
             PyErr_Format(PyExc_TypeError,
             "Unable to store %s object in %s type array.",
@@ -48,7 +49,7 @@ static int set_exception_if_dtype_mismatch(PyObject* value, PyObject* dtype) {
 }
 
 static int raise_exception_if_dtype_mismatch(PyObject* value, PyObject* dtype) {
-    if( !PyObject_IsInstance(value, dtype) ) {
+    if ( !PyObject_IsInstance(value, dtype) ) {
         PyErr_Format(PyExc_TypeError,
         "Unable to store %s object in %s type array.",
         PyObject_AsString(PyObject_Repr(PyObject_Type(value))),
@@ -74,18 +75,18 @@ static int _check_type(PyObject* arg, PyTypeObject* type) {
 static int _comp(PyObject* u, PyObject* v, PyObject* tcomp) {
     int u_isNone = u == Py_None;
     int v_isNone = v == Py_None;
-    if( u_isNone && !v_isNone) {
+    if ( u_isNone && !v_isNone) {
         return 0;
     }
-    if( !u_isNone && v_isNone ) {
+    if ( !u_isNone && v_isNone ) {
         return 1;
     }
-    if( u_isNone && v_isNone ) {
+    if ( u_isNone && v_isNone ) {
         return 0;
     }
-    if( tcomp ) {
+    if ( tcomp ) {
         PyObject* result_PyObject = PyObject_CallFunctionObjArgs(tcomp, u, v, NULL);
-        if( !result_PyObject ) {
+        if ( !result_PyObject ) {
             PyErr_Format(PyExc_ValueError,
                 "Unable to compare %s object with %s object.",
                 PyObject_AsString(PyObject_Repr(PyObject_Type(u))),
@@ -96,7 +97,7 @@ static int _comp(PyObject* u, PyObject* v, PyObject* tcomp) {
     }
 
     int result = PyObject_RichCompareBool(u, v, Py_LE);
-    if( result == -1 ) {
+    if ( result == -1 ) {
         PyErr_Format(PyExc_ValueError,
             "Unable to compare %s object with %s object.",
             PyObject_AsString(PyObject_Repr(PyObject_Type(u))),
diff --git a/pydatastructs/utils/_extensions.py b/pydatastructs/utils/_extensions.py
new file mode 100644
index 000000000..e7f531827
--- /dev/null
+++ b/pydatastructs/utils/_extensions.py
@@ -0,0 +1,17 @@
+from setuptools import Extension
+
+project = 'pydatastructs'
+
+module = 'utils'
+
+backend = '_backend'
+
+cpp = 'cpp'
+
+nodes = '.'.join([project, module, backend, cpp, '_nodes'])
+nodes_sources = ['/'.join([project, module, backend, cpp,
+                            'nodes.cpp'])]
+
+extensions = [
+    Extension(nodes, sources=nodes_sources)
+]
diff --git a/pydatastructs/utils/misc_util.py b/pydatastructs/utils/misc_util.py
index f186dfe91..7a4caf606 100644
--- a/pydatastructs/utils/misc_util.py
+++ b/pydatastructs/utils/misc_util.py
@@ -1,5 +1,6 @@
 import math, pydatastructs
 from enum import Enum
+from pydatastructs.utils._backend.cpp import _nodes
 
 __all__ = [
     'TreeNode',
@@ -72,8 +73,9 @@ def methods(cls):
         return ['__new__', '__str__']
 
     def __new__(cls, key, data=None, **kwargs):
-        raise_if_backend_is_not_python(
-            cls, kwargs.get('backend', Backend.PYTHON))
+        backend = kwargs.get('backend', Backend.PYTHON)
+        if backend == Backend.CPP:
+            return _nodes.TreeNode(key, data, **kwargs)
         obj = Node.__new__(cls)
         obj.data, obj.key = data, key
         obj.left, obj.right, obj.parent, obj.height, obj.size = \
diff --git a/scripts/build/dummy_submodules_data.py b/scripts/build/dummy_submodules_data.py
index 2fa19414c..ea3d63228 100644
--- a/scripts/build/dummy_submodules_data.py
+++ b/scripts/build/dummy_submodules_data.py
@@ -1,9 +1,9 @@
 project = 'pydatastructs'
 
-modules = ['linear_data_structures', 'miscellaneous_data_structures']
+modules = ['linear_data_structures', 'miscellaneous_data_structures', 'utils', 'trees']
 
 backend = '_backend'
 
 cpp = 'cpp'
 
-dummy_submodules_list = [('_arrays.py', '_algorithms.py'), ('_stack.py',)]
+dummy_submodules_list = [('_arrays.py', '_algorithms.py'), ('_stack.py',), ('_nodes.py',), ('_trees.py',)]
diff --git a/setup.py b/setup.py
index 58cffd677..60c4ec36d 100644
--- a/setup.py
+++ b/setup.py
@@ -1,14 +1,18 @@
 import setuptools
+from pydatastructs import utils
 from pydatastructs import linear_data_structures
 from pydatastructs import miscellaneous_data_structures
+from pydatastructs import trees
 
 with open("README.md", "r") as fh:
     long_description = fh.read()
 
 extensions = []
 
+extensions.extend(utils._extensions.extensions)
 extensions.extend(linear_data_structures._extensions.extensions)
 extensions.extend(miscellaneous_data_structures._extensions.extensions)
+extensions.extend(trees._extensions.extensions)
 
 setuptools.setup(
     name="cz-pydatastructs",


Test patch:
diff --git a/pydatastructs/linear_data_structures/tests/benchmarks/test_algorithms.py b/pydatastructs/linear_data_structures/tests/benchmarks/test_algorithms.py
index 537d288af..da676c69c 100644
--- a/pydatastructs/linear_data_structures/tests/benchmarks/test_algorithms.py
+++ b/pydatastructs/linear_data_structures/tests/benchmarks/test_algorithms.py
@@ -41,9 +41,6 @@ def test_quick_sort():
 def test_bubble_sort():
     _test_common_sort(bubble_sort, size=2000)
 
-@pytest.mark.xfail
-def test_intro_sort():
-     _test_common_sort(intro_sort, size=2000)
 
 @pytest.mark.xfail
 def test_selection_sort():
diff --git a/pydatastructs/linear_data_structures/tests/test_arrays.py b/pydatastructs/linear_data_structures/tests/test_arrays.py
index a6b881486..496978991 100644
--- a/pydatastructs/linear_data_structures/tests/test_arrays.py
+++ b/pydatastructs/linear_data_structures/tests/test_arrays.py
@@ -1,9 +1,9 @@
 from pydatastructs.linear_data_structures import (
     OneDimensionalArray, DynamicOneDimensionalArray,
-    MultiDimensionalArray)
+    MultiDimensionalArray, ArrayForTrees)
 from pydatastructs.utils.misc_util import Backend
 from pydatastructs.utils.raises_util import raises
-
+from pydatastructs.utils import TreeNode
 
 def test_OneDimensionalArray():
     ODA = OneDimensionalArray
@@ -127,3 +127,24 @@ def test_DynamicOneDimensionalArray():
     b.append(4)
     b.append(5)
     assert [b[i] for i in range(b.size)] == [1, 2, 3, 4, 5, None, None]
+
+def test_DynamicOneDimensionalArray2():
+    DODA = DynamicOneDimensionalArray
+    root = TreeNode(1, 100)
+    A = DODA(TreeNode, [root])
+    assert str(A[0]) == "(None, 1, 100, None)"
+
+def _test_ArrayForTrees(backend):
+     AFT = ArrayForTrees
+     root = TreeNode(1, 100)
+     A = AFT(TreeNode, [root], backend=backend)
+     assert str(A) == "['(None, 1, 100, None)']"
+     node = TreeNode(2, 200, backend=backend)
+     A.append(node)
+     assert str(A) == "['(None, 1, 100, None)', '(None, 2, 200, None)']"
+
+def test_ArrayForTrees():
+    _test_ArrayForTrees(Backend.PYTHON)
+
+def test_cpp_ArrayForTrees():
+    _test_ArrayForTrees(Backend.CPP)
diff --git a/pydatastructs/trees/tests/benchmarks/test_binary_trees.py b/pydatastructs/trees/tests/benchmarks/test_binary_trees.py
new file mode 100644
index 000000000..c0ab14ce4
--- /dev/null
+++ b/pydatastructs/trees/tests/benchmarks/test_binary_trees.py
@@ -0,0 +1,50 @@
+import timeit, functools, os, pytest
+from pydatastructs.trees.binary_trees import (BinarySearchTree)
+from pydatastructs.utils.misc_util import Backend
+
+@pytest.mark.xfail
+def test_BinarySearchTree(**kwargs):
+    cpp = Backend.CPP
+    repeat = 1
+    number = 1
+
+    size = int(os.environ.get("PYDATASTRUCTS_BENCHMARK_SIZE", "1000"))
+    size = kwargs.get("size", size)
+
+    BST = BinarySearchTree
+    b1 = BST(backend=Backend.PYTHON)
+    b2 = BST(backend=Backend.CPP)
+
+    def f(backend, tree):
+        for node in range(-1000,1000):
+            tree.insert(node, node)
+    def g(backend, tree):
+        for node in range(-1000, 1000):
+            tree.search(node)
+    def h(backend, tree):
+        for node in range(2000):
+            tree.delete(node)
+
+    kwds_dict_PY = {"backend": Backend.PYTHON, "tree":b1}
+    kwds_dict_CPP = {"backend": Backend.CPP, "tree":b2}
+
+    timer_python = timeit.Timer(functools.partial(f, **kwds_dict_PY))
+    python_insert = min(timer_python.repeat(repeat, number))
+
+    timer_cpp = timeit.Timer(functools.partial(f, **kwds_dict_CPP))
+    cpp_insert = min(timer_cpp.repeat(repeat, number))
+    assert cpp_insert < python_insert
+
+    timer_python = timeit.Timer(functools.partial(g, **kwds_dict_PY))
+    python_search = min(timer_python.repeat(repeat, number))
+
+    timer_cpp = timeit.Timer(functools.partial(g, **kwds_dict_CPP))
+    cpp_search = min(timer_cpp.repeat(repeat, number))
+    assert cpp_search < python_search
+
+    timer_python = timeit.Timer(functools.partial(h, **kwds_dict_PY))
+    python_delete = min(timer_python.repeat(repeat, number))
+
+    timer_cpp = timeit.Timer(functools.partial(h, **kwds_dict_CPP))
+    cpp_delete = min(timer_cpp.repeat(repeat, number))
+    assert cpp_delete < python_delete
diff --git a/pydatastructs/trees/tests/test_binary_trees.py b/pydatastructs/trees/tests/test_binary_trees.py
index ef901db76..fc5b98923 100644
--- a/pydatastructs/trees/tests/test_binary_trees.py
+++ b/pydatastructs/trees/tests/test_binary_trees.py
@@ -1,14 +1,15 @@
 from pydatastructs.trees.binary_trees import (
-    BinarySearchTree, BinaryTreeTraversal, AVLTree,
+    BinaryTree, BinarySearchTree, BinaryTreeTraversal, AVLTree,
     ArrayForTrees, BinaryIndexedTree, SelfBalancingBinaryTree, SplayTree, CartesianTree, Treap, RedBlackTree)
 from pydatastructs.utils.raises_util import raises
 from pydatastructs.utils.misc_util import TreeNode
 from copy import deepcopy
+from pydatastructs.utils.misc_util import Backend
 import random
 
-def test_BinarySearchTree():
+def _test_BinarySearchTree(backend):
     BST = BinarySearchTree
-    b = BST(8, 8)
+    b = BST(8, 8, backend=backend)
     b.delete(8)
     b.insert(8, 8)
     b.insert(3, 3)
@@ -25,7 +26,12 @@ def test_BinarySearchTree():
     "(5, 6, 6, 6), (None, 4, 4, None), (None, 7, 7, None), (8, 14, 14, None), "
     "(None, 13, 13, None)]")
 
-    trav = BinaryTreeTraversal(b)
+    assert b.tree[0].left == 1
+    assert b.tree[0].key == 8
+    assert b.tree[0].data == 8
+    assert b.tree[0].right == 2
+
+    trav = BinaryTreeTraversal(b, backend=backend)
     in_order = trav.depth_first_search(order='in_order')
     pre_order = trav.depth_first_search(order='pre_order')
     assert [node.key for node in in_order] == [1, 3, 4, 6, 7, 8, 10, 13, 14]
@@ -56,10 +62,10 @@ def test_BinarySearchTree():
     assert [node.key for node in in_order] == [8, 14]
     assert [node.key for node in pre_order] == [8, 14]
 
-    bc = BST(1, 1)
+    bc = BST(1, 1, backend=backend)
     assert bc.insert(1, 2) is None
 
-    b = BST(-8, 8)
+    b = BST(-8, 8, backend=backend)
     b.insert(-3, 3)
     b.insert(-10, 10)
     b.insert(-1, 1)
@@ -68,11 +74,14 @@ def test_BinarySearchTree():
     b.insert(-7, 7)
     b.insert(-14, 14)
     b.insert(-13, 13)
-    assert b.delete(-13) is True
-    assert b.delete(-10) is True
-    assert b.delete(-3) is True
-    assert b.delete(-13) is None
-    bl = BST()
+
+    b.delete(-13)
+    b.delete(-10)
+    b.delete(-3)
+    b.delete(-13)
+    assert str(b) == "[(7, -8, 8, 1), (4, -1, 1, None), '', '', (6, -6, 6, 5), (None, -4, 4, None), (None, -7, 7, None), (None, -14, 14, None)]"
+
+    bl = BST(backend=backend)
     nodes = [50, 30, 90, 70, 100, 60, 80, 55, 20, 40, 15, 10, 16, 17, 18]
     for node in nodes:
         bl.insert(node, node)
@@ -105,10 +114,16 @@ def test_BinarySearchTree():
     assert raises(ValueError, lambda: bl.lowest_common_ancestor(200, 60, 1))
     assert raises(ValueError, lambda: bl.lowest_common_ancestor(-3, 4, 1))
 
-def test_BinaryTreeTraversal():
+def test_BinarySearchTree():
+    _test_BinarySearchTree(Backend.PYTHON)
+
+def test_cpp_BinarySearchTree():
+    _test_BinarySearchTree(Backend.CPP)
+
+def _test_BinaryTreeTraversal(backend):
     BST = BinarySearchTree
     BTT = BinaryTreeTraversal
-    b = BST('F', 'F')
+    b = BST('F', 'F', backend=backend)
     b.insert('B', 'B')
     b.insert('A', 'A')
     b.insert('G', 'G')
@@ -117,7 +132,8 @@ def test_BinaryTreeTraversal():
     b.insert('E', 'E')
     b.insert('I', 'I')
     b.insert('H', 'H')
-    trav = BTT(b)
+
+    trav = BTT(b, backend=backend)
     pre = trav.depth_first_search(order='pre_order')
     assert [node.key for node in pre] == ['F', 'B', 'A', 'D', 'C', 'E', 'G', 'I', 'H']
 
@@ -137,6 +153,12 @@ def test_BinaryTreeTraversal():
     assert raises(NotImplementedError, lambda: trav.depth_first_search(order='in_out_order'))
     assert raises(TypeError, lambda: BTT(1))
 
+def test_BinaryTreeTraversal():
+    _test_BinaryTreeTraversal(Backend.PYTHON)
+
+def test_cpp_BinaryTreeTraversal():
+    _test_BinaryTreeTraversal(Backend.CPP)
+
 def test_AVLTree():
     a = AVLTree('M', 'M')
     a.insert('N', 'N')
@@ -338,6 +360,7 @@ def test_select_rank(expected_output):
     a5.delete(2)
     test_select_rank([])
 
+
 def test_BinaryIndexedTree():
 
     FT = BinaryIndexedTree
@@ -352,6 +375,7 @@ def test_BinaryIndexedTree():
     assert t.get_sum(0, 4) == 114
     assert t.get_sum(1, 9) == 54
 
+
 def test_CartesianTree():
     tree = CartesianTree()
     tree.insert(3, 1, 3)
diff --git a/pydatastructs/utils/tests/test_misc_util.py b/pydatastructs/utils/tests/test_misc_util.py
index 520d26044..0e253c9a2 100644
--- a/pydatastructs/utils/tests/test_misc_util.py
+++ b/pydatastructs/utils/tests/test_misc_util.py
@@ -1,6 +1,11 @@
-from pydatastructs.utils import (AdjacencyListGraphNode, AdjacencyMatrixGraphNode,
+from pydatastructs.utils import (TreeNode, AdjacencyListGraphNode, AdjacencyMatrixGraphNode,
                                 GraphEdge, BinomialTreeNode, MAryTreeNode, CartesianTreeNode, RedBlackTreeNode, SkipNode)
 from pydatastructs.utils.raises_util import raises
+from pydatastructs.utils.misc_util import Backend
+
+def test_cpp_TreeNode():
+    n = TreeNode(1,100,backend=Backend.CPP)
+    assert str(n) == "(None, 1, 100, None)"
 
 def test_AdjacencyListGraphNode():
     g_1 = AdjacencyListGraphNode('g_1', 1)