Oct 11, 2018 · Oct 10, 2018 · Oct 10, 2018 · Oct 10, 2018 · Oct 10, 2018 · Oct 10, 2018
diff --git a/allalgorithms/sorting/__init__.py b/allalgorithms/sorting/__init__.py
 from .pidgeonhole_sort import pidgeonhole_sort
 from .stooge_sort import stooge_sort
 from .cocktail_shaker_sort import cocktail_shaker_sort
 from .tree_sort import tree_sort
diff --git a/allalgorithms/sorting/tree_sort.py b/allalgorithms/sorting/tree_sort.py
 class BinaryTreeNode(object):
    #initial values for value,left and right
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


 # inserting a new node in the binary tree
 def insert(tree, item):
    # if no initial element in the tree
    if tree == None:
        tree = BinaryTreeNode(item)
    else:
        if (item < tree.value):
            # if left branch of the tree is empty
            if (tree.left == None):
                tree.left = BinaryTreeNode(item)
            else:
                insert(tree.left, item)
        else:
            # if right branch of the tree is empty
            if (tree.right == None):
                tree.right = BinaryTreeNode(item)
            else:
                insert(tree.right, item)
    return tree

 # funtion for the inorder traversal of the binary tree
 def in_order_traversal(tree,a):
    if (tree.left != None):
        in_order_traversal(tree.left,a)
    a.append(tree.value)
    if (tree.right != None):
        in_order_traversal(tree.right,a)


 def tree_sort(x):
    # root node
    t = insert(None, x[0]);
    # inserting all elements in the binary tree
    for i in x[1:]:
        insert(t,i)
    # the results of the inorder traversal of a binary tree is a sorted
    a = []
    in_order_traversal(t,a)
    return a

diff --git a/docs/sorting/tree-sort.md b/docs/sorting/tree-sort.md
 # Tree Sort

 A tree sort is a sort algorithm that builds a binary search tree from the elements to be sorted, and then traverses the tree (in-order) so that the elements come out in sorted order. It has two phases:
 1. Frist is creating a binary search tree using the given array elements.
 2. Second phase is traversing the given binary search tree in inorder, thus resulting in a sorted array.

 **Performance**

 The average number of comparisions for this method is O(nlogn). But in worst case, number of comparisions is reduced by O(n^2), a case which arrives when the tree is skewed.



 ## Install

 ```
 pip install allalgorithms
 ```

 ## Usage

 ```py
 from allalgorithms.sorting import tree_sort

 arr = [77, 2, 10, -2, 1, 7]

 print(tree_sort(arr))
 # -> [-2, 1, 2, 7, 10, 77]
 ```

 ## API

 ### tree_sort(array)

 > Returns a sorted array

 ##### Params:

 - `array`: Unsorted Array
diff --git a/tests/test_sorting.py b/tests/test_sorting.py
    selection_sort,
    pidgeonhole_sort,
    stooge_sort,
    cocktail_shaker_sort
    cocktail_shaker_sort,
    tree_sort
 )



    def test_cocktail_shaker_sort(self):
        self.assertEqual([-44, 1, 2, 3, 7, 19], cocktail_shaker_sort([7, 3, 2, 19, -44, 1]))

    def tree_sort(self):
        self.assertEqual([-44, 1, 2, 3, 7, 19], tree_sort([7, 3, 2, 19, -44, 1]))


 if __name__ == "__main__":
Original file line number	Diff line number	Diff line change
Expand Up		@@ -5,3 +5,4 @@
		from .pidgeonhole_sort import pidgeonhole_sort
		from .stooge_sort import stooge_sort
		from .cocktail_shaker_sort import cocktail_shaker_sort
		from .tree_sort import tree_sort
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,48 @@
		class BinaryTreeNode(object):
		#initial values for value,left and right
		def __init__(self, value):
		self.value = value
		self.left = None
		self.right = None


		# inserting a new node in the binary tree
		def insert(tree, item):
		# if no initial element in the tree
		if tree == None:
		tree = BinaryTreeNode(item)
		else:
		if (item < tree.value):
		# if left branch of the tree is empty
		if (tree.left == None):
		tree.left = BinaryTreeNode(item)
		else:
		insert(tree.left, item)
		else:
		# if right branch of the tree is empty
		if (tree.right == None):
		tree.right = BinaryTreeNode(item)
		else:
		insert(tree.right, item)
		return tree

		# funtion for the inorder traversal of the binary tree
		def in_order_traversal(tree,a):
		if (tree.left != None):
		in_order_traversal(tree.left,a)
		a.append(tree.value)
		if (tree.right != None):
		in_order_traversal(tree.right,a)


		def tree_sort(x):
		# root node
		t = insert(None, x[0]);
		# inserting all elements in the binary tree
		for i in x[1:]:
		insert(t,i)
		# the results of the inorder traversal of a binary tree is a sorted
		a = []
		in_order_traversal(t,a)
		return a
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,38 @@
		# Tree Sort

		A tree sort is a sort algorithm that builds a binary search tree from the elements to be sorted, and then traverses the tree (in-order) so that the elements come out in sorted order. It has two phases:
		1. Frist is creating a binary search tree using the given array elements.
		2. Second phase is traversing the given binary search tree in inorder, thus resulting in a sorted array.

		Performance

		The average number of comparisions for this method is O(nlogn). But in worst case, number of comparisions is reduced by O(n^2), a case which arrives when the tree is skewed.



		## Install

		```
		pip install allalgorithms
		```

		## Usage

		```py
		from allalgorithms.sorting import tree_sort

		arr = [77, 2, 10, -2, 1, 7]

		print(tree_sort(arr))
		# -> [-2, 1, 2, 7, 10, 77]
		```

		## API

		### tree_sort(array)

		> Returns a sorted array

		##### Params:

		- `array`: Unsorted Array
Original file line number	Diff line number	Diff line change
Expand Up		@@ -7,7 +7,8 @@
		selection_sort,
		pidgeonhole_sort,
		stooge_sort,
		cocktail_shaker_sort
		cocktail_shaker_sort,
		tree_sort
		)


Expand All		@@ -32,6 +33,9 @@ def test_stooge_sort(self):

		def test_cocktail_shaker_sort(self):
		self.assertEqual([-44, 1, 2, 3, 7, 19], cocktail_shaker_sort([7, 3, 2, 19, -44, 1]))

		def tree_sort(self):
		self.assertEqual([-44, 1, 2, 3, 7, 19], tree_sort([7, 3, 2, 19, -44, 1]))


		if __name__ == "__main__":
Expand Down