Binary Tree Sort Algorithm (Python)

Question

A Binary Tree Sort is an 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.

Average Case Time Complexity : O(N log N) adding one element to a Binary Search Tree on average takes O(log N) time (height of a tree). Therefore, adding n elements will take O(N log N) time.

Worst Case Time Complexity : O(N^2). The worst case can be improved by using a self-balancing binary search tree, which will take O(N log N) time to sort the array in worst case.

---

Just for practicing, I've implemented the Binary Tree Sort algorithm, and if you'd like to review the code and provide any change/improvement recommendations, please do so, and I appreciate that.

---

Code

"""
This module creates a Binary Sort Tree ascendingly using In Order Tree Traverse;
Stable Sort;
Worst Case Time Complexity (For if the tree would be a chain Tree): O(N^2)
Average Case Time Complexity: O(N^Log N)
Memory Complexity: Not in place O(N)
"""

import random
from typing import List, TypeVar

T = TypeVar('T')

# Not sure how to design and handle the exceptions here yet
class ExceptionHandling(Exception):
    pass


class Node(object):
    def __init__(self, node_value: int) -> None:
        """
        Initializes a node with three attributes;
        `node_value` (Node Value): Must be an integer/float;
        `right_child` (Right Child): Initializes to `None`; Its value must be larger than the Root Node;
        `left_child` (Left Child): Initializes to `None`; Its value must be smaller than the Root Node;
        """
        self.node_value = node_value
        self.right_child = None
        self.left_child = None


class BinarySearchTree(object):
    def __init__(self) -> None:
        """
        Initializes the Root Node of the Binary Tree to None;
        """
        self.root = None

    def is_empty(self) -> bool:
        """
        Returns True if the tree doesn't have a node;
        """
        return self.root == None

    def insert(self, new_node: int) -> None:
        """
        Inserts an integer-value Node in the Tree;
        """
        self.root = self._insert(self.root, new_node)

    def _insert(self, parent: int, new_node: int) -> int:
        """
        Inserts an integer value in the left or right Node; 
        Returns the parent Node;
        """
        # If tree is empty
        if parent is None:
            parent = Node(new_node)
        # If the new Node value is smaller than its parent Node value
        elif new_node < parent.node_value:
            parent.left_child = self._insert(parent.left_child, new_node)
        # If the new Node value is bigger than its parent Node value
        else:
            parent.right_child = self._insert(parent.right_child, new_node)

        return parent

    def inorder(self) -> None:
        """
        Calls the _inorder traversing method;
        """
        self._inorder(self.root)

    def _inorder(self, parent: int) -> None:
        """
        Traverses the tree inorder (Left Node, Root Node, Right Node)
        """
        if parent is None:
            return
        self._inorder(parent.left_child)
        print(f'{parent.node_value}')
        self._inorder(parent.right_child)


if __name__ == '__main__':

    tree = BinarySearchTree()

    for i in range(random.randint(20, 30)):
        tree.insert(random.uniform(-10, 10))

    tree.inorder()

Sources

• Tree Sort - Wiki

• Tree Sort - Geeks for Geeks

Answer 1

Type Hints

From these lines:

from typing import List, TypeVar

T = TypeVar('T')

it looks like you intend to add type-hints for a type T to you code. But nowhere are you using T as a type hint. You probably wanted to actually use T, such as like:

def __init__(self, node_value: T) -> None

Either that, or delete the typing code.

Exception Handling

You have:

class ExceptionHandling(Exception):
    pass

but nowhere are you actually executing raise ExceptionHandling("Your error message"). Moreover, nowhere do I actually see a need to raise an exception; you aren't doing anything that could fail. Until you have a need for raising your own custom exception, you could remove this code.

class Node(object):

Since you are using f-strings, it is clear, you are using Python 3. In Python 3+, you don't need to inherit from object; it is automatically implied.

Names & Types

def insert(self, new_node: int) -> None:

Is new_node a Node or an int? The variable name suggests it would be a Node, but it is typed as an int. When you use it, you are passing in an int. Maybe new_value would be clearer?

def _insert(self, parent: int, new_node: int) -> int:

Now we're definitely confused. Is parent an int? Does this function return an int? Both seem to be a definite "no". Those types should be Node. And again, new_node should be renamed, because it isn't a Node.

Method naming (and docstrings)

What does inorder do? I'd expect it to return the contents of the tree "in order". But the type-hint says it returns None, so that is not correct. Let's consult help:

>>> help(BinarySearchTree.inorder)
Help on function inorder in module __main__:

inorder(self) -> None
    Calls the _inorder traversing method;

>>>

Well, that's entirely unhelpful. It calls a private _inorder traversing method. Ok, but what does it do???

Name functions based on what they do. Your inorder function prints the tree in order, so name it with print in its name, such as print_inorder.

Also, write docstrings to tell a caller what the function does. Use a high-level description. Include any requirements, preconditions and/or postconditions. Do not include implementation details. The caller cares only about what it does and how to use the function properly; they only care the function works, not how it works.

def print_inorder(self) -> None:
    """
    Print the tree in ascending order, one element per line, to sys.stdout
    """
    self._inorder(self.root)

Finally, your class is named BinarySearchTree, yet it provides no methods for searching. Hmm.

Pointless f-string

The statement:

print(f'{parent.node_value}')

is a complicated way of writing:

print(parent.node_value)

Algorithm

Your insert / _insert functions are overly complicated. There is no need to use recursion. Moreover, returning the parent from _insert is mostly useless, because the caller is passing parent to the function; it only matters when the caller passes None in as the parent.

A non-recursive approach:

def insert(self, new_value: int) -> None:

    new_node = Node(new_value)

    if self.root:
        parent = self.root
        while True:
            if new_value < parent.node_value:
                if parent.left_child:
                    parent = parent.left_child
                else:
                    parent.left_child = new_node
                    break
            else:
                if parent.right_child:
                    parent = parent.right_child
                else:
                    parent.right_child = new_node
                    break
    else:
        self.root = new_node

Possible Improvements

Encapsulation

Node is an internal detail of the BinarySearchTree. You could make it an internal class:

class BinarySearchTree:

    class Node:
        def __init__(self, node_value:T ) -> None:
            self.node_value = node_value
            self.right_child = None
            self.left_child = None

    def __init__(self) -> None
        self.root = None

    ...


       parent = BinarySearchTree.Node(new_node)

    ...

Iterator

Instead of the method inorder printing the contents of the tree, perhaps it could return an iterator which would traverse the tree returning elements one at a time. The caller could then print them, or perform whatever operation they desired.

for value in tree.inorder():
    print(value)

Instead of naming this iterator creating function inorder, it could be named __iter__, in which case, the caller would just need to write:

for value in tree:
    print(value)

You'd create this iterator in one of two ways. The "hard way", returning a new iterator object, with a __next__ method. Or the "easy way" using a generator function, using yield and yield from statements.

Answer 2

Exceptions

# Not sure how to design and handle the exceptions here yet

Your syntax is more or less fine, though you'll obviously want to rename the exception class. The purpose of an exception like this is to allow you to raise something specific to your application that consumer code might be interested in catching. One place you could potentially raise:

    if parent is None:
        return

It's unlikely that silent-fail is the right thing to do, here.

is None

This:

return self.root == None

should probably be

return self.root is None

Member types

These assignments:

    self.right_child = None
    self.left_child = None

should receive type hints, since it's not obvious what they'll eventually receive. My guess is

self.right_child: Node = None
self.left_child: Node = None

English is not C;

You have a funny habit of terminating your comments with semicolons. That isn't necessary.

Node value types

node_value (Node Value): Must be an integer/float

So which is it - an integer, or a float? Given that your usage of this value only requires that it be comparable, I'd suggest float.

Answer 3

I don't know about this typevar but it seems over complicated. Why are you specifying the type and using two classes when you need only one. Here's my solution.

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
    def add(self, val):
        if val < self.val:
            if self.left == None:
                self.left = Node(val)
            else:
                self.left.add(val)
        else:
            if self.right == None:
                self.right = Node(val)
            else:
                self.right.add(val)
    def sort(self):
        a = []
        b = [self.val]
        c = []
        if self.left:
            a = self.left.sort()
        if self.right:
            c = self.right.sort()
        return a+b+c
    def str(self):
        a, b = "", ""
        if self.left:
            a = self.left.str()
        if self.right:
            b = self.right.str()
        return "({}, {}, {})".format(self.val, a, b)
def tree_sort(s):
    node = Node(s[0])
    for val in s[1:]:
        node.add(val)
    return node.sort()

l=[123, 48, 23, 100, 56,2, 10, 273, 108, 398, 100, 2651, 12]
print(tree_sort(l))