Type Hints

From these lines:

from typing import List, TypeVarT = TypeVar('T')

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

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

Either that, or delete thetyping code.

Exception Handling

You have:

class ExceptionHandling(Exception):    pass

but nowhere are you actually executingraise 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 fromobject; it is automatically implied.

Names & Types

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

Isnew_node aNode or anint? The variable name suggests it would be aNode, but it is typed as anint. When you use it, you are passing in an int. Maybenew_value would be clearer?

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

Now we're definitely confused. Isparent anint? Does this function return anint? Both seem to be a definite "no". Those types should beNode. And again,new_node should be renamed, because it isn't aNode.

Method naming (and docstrings)

What doesinorder do? I'd expect it to return the contents of the tree "in order". But the type-hint says it returnsNone, 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. Yourinorder functionprints the tree in order, so name it withprint in its name, such asprint_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 namedBinarySearchTree, 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

Yourinsert /_insert functions are overly complicated. There is no need to use recursion. Moreover, returning theparent from_insert is mostly useless, because the caller is passingparent to the function; it only matters when the caller passesNone 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 theBinarySearchTree. 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 methodinorder 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 functioninorder, 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, usingyield andyield from statements.

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 toraise 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 = Noneself.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 suggestfloat.

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))

• 2
  \$\begingroup\$Welcome to Code Review. Your answer does focus on an alternative implementation, while answers should preferably focus on a review of the code/approach provided. There are many binary-sort questions on Code Review, what makes your answer specific to this question?\$\endgroup\$

  Mast

  – Mast♦

  2020-07-04 09:54:59 +00:00

  CommentedJul 4, 2020 at 9:54

• python
• beginner
• algorithm
• object-oriented
• sorting