Binary Search Tree (BST) Implementation

Question

This is the first Time implementing a Binary Search Tree, based on how it works from the visualgo website. I made this algorithm purely based on what I saw, and the remove method was quite challenging. How can I improve the speed/efficiency and make the code look better?

Methods:

• Inorder: basically an inorder traversal through the BST Ex: 1 3 4 6 19 25
• Insert: inserts a node with a certain value
• lookup: returns the value if it exists in the BST else returns None
• getMin: returns the min value in the specified node
• remove: removes a value, and if current_node is not specified then, it starts from the root node, a bit recursive, even though I wanted to implement a way without recursion, but I couldn't see it working without it in any way.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def inorder(self, current_node):
        if current_node:  
            self.inorder(current_node.left)
            print(current_node.value, end=' ')
            self.inorder(current_node.right)

    def insert(self, value):
        NewNode = Node(value) 
        current_node = self.root
        if current_node is None:
            self.root = NewNode
        else:
            while True:
                if value < current_node.value:
                    #Left
                    if not current_node.left:
                        current_node.left = NewNode
                        return self
                    current_node = current_node.left
                else:
                    if not current_node.right:
                        current_node.right = NewNode
                        return self
                    current_node = current_node.right

    def lookup(self, value):
        current_node = self.root
        if current_node is None:
            return None
        while current_node:
            current_value = current_node.value
            if value < current_value:
                current_node = current_node.left
            elif value > current_value:
                current_node = current_node.right
            else:
                return current_node

    def getMin(self, current_node):
        while current_node.left is not None:
            current_node = current_node.left
        return current_node.value

    def remove(self, value, current_node=False):
        if not current_node:
            current_node = self.root

        if not current_node: # if the root is None
            return None

        parent_node = None
        while current_node:
            current_value = current_node.value
            if value < current_value:   
                parent_node = current_node
                current_node = current_node.left
            elif value > current_value:
                parent_node = current_node
                current_node = current_node.right
            else:
                # No Child
                if not current_node.left and not current_node.right:
                    if parent_node is None:
                        self.root = None
                    elif current_node == parent_node.left:
                        parent_node.left = None
                    else:
                        parent_node.right = None

                # One Child
                elif current_node.right and not current_node.left:
                    if parent_node is None:
                        self.root = current_node.right
                    elif current_node == parent_node.left:
                        parent_node.left = current_node.right
                    else:
                        parent_node.right = current_node.right

                elif current_node.left and not current_node.right:
                    if parent_node is None:
                        self.root = current_node.left
                    elif current_node == parent_node.left:
                        parent_node.left = current_node.left
                    else:
                        parent_node.right = current_node.left

                # Two Child
                else:
                    in_order_successor = self.getMin(current_node.right)

                    self.remove(in_order_successor, current_node)
                    if parent_node is None:
                        self.root.value = in_order_successor
                    elif current_node == parent_node.left:
                        parent_node.left.value = in_order_successor
                    else:
                        parent_node.right.value = in_order_successor
                return True # if removed

        return False # if value doesnt exist                

Answer 1

How can I…make the code look better?

Follow the Style Guide for Python Code.
Add docstrings, at least for "everything to be used externally".
Add (doc)tests. Or, at least, a start for tinkering:

if __name__ == "__main__":
    t = BinarySearchTree()
    for c in "badcef":
        t.insert(c)
    t.remove("d")

provide amenities like an __str__ for node

    def is_leaf(self):
        return self.left is None and self.right is None

    def __str__(self):
        return "(" + (self.value if self.is_leaf() else (
            (str(self.left.value + "<") if self.left else "^")
            + self.value
            + ("<" + str(self.right.value) if self.right else "^"))) + ")"

(It is somewhat rare that I don't provide docstrings. It felt right here.)

Keep classes and functions short.
 Say, 24 lines for "heads", 48 for a function body, 96 for a class.

Where not impeding readability, keep nesting level low.
 This includes early outs, continues, breaks & else in loops; returns

    def insert(self, value):
        """ Insert value into this tree.
            ToDo: document behaviour with identical keys
                  (what about lookup()?)
        """
        latest = Node(value)
        current = self.root
        previous = None     # the parent for latest, if any
        left = None         # the child latest is going to be in parent
        while current is not None:
            previous = current
            left = value < current.value
            current = current.left if left else current.right
        if previous is None:
            self.root = latest
        elif left:
            previous.left = latest
        else:
            previous.right = latest
        return self

(what an awful example for changing entirely too many things at once)

Python naming style is CapWords for classes, only: that would be new_node.
The left = None statement is there for the comment.
The paranoid prefer is None/is not None over just using what should be a reference in a boolean context. Above rendition tries to keep DRY and avoids some of what looks repetitious in the insert() you presented.
But, wait, doesn't that descend left or right thing look just the same in lookup() and remove()?
If I had a method

    def _find(self, value):
        """ Find node with value, if any.
            Return this node and setter for (re-)placing it in this tree.
        """
        pass

, insert() was simple, and lookup() trivial (if questionable: wording
• lookup: returns the value if it exists in the BST else returns None
, implementation returns a Node):

    def insert(self, value):
        """ Insert value into this tree.
            ToDo: document behaviour with identical keys
        """
        existing, place = self._find(value)
        if existing is not None:
            pass
        place(Node(value))
        return self
    
    def lookup(self, value):
        """ Return node with value, if any. """
        return self._find(value)[0]

Remove can profit from a modified successor method

    @staticmethod
    def leftmost(child, parent=None):
        """ Return the leftmost node of the tree rooted at child,
            and its parent, if any. """
        if child is not None:
            while child.left is not None:
                child, parent = child.left, child
        return child, parent
    
    def deleted(self, node):  # node None?
        """ Return root of a tree with node's value deleted. """
        successor, parent = BinarySearchTree.leftmost(node.right, node)
        if successor is None:
            return node.left
        node.value = successor.value
        if node is not parent:
            parent.left = successor.right
        else:
            node.right = successor.right
        return node
    
    def remove(self, value):
        """ Remove value.
            Return 'tree contained value'. """
        node, place = self._find(value)
        if node is None:
            return False
        place(self.deleted(node))
        return True

My current rendition of _find() adds in Node

    def _set_left(self, v):
        self.left = v
    
    def _set_right(self, v):
        self.right = v

, in BinarySearchTree

    def _set_root(self, v):
        self.root = v
    
    def _find(self, value):
        """ Find node with value, if any.
            Return this node and setter for (re-)placing it in this tree.
        """
        if self.root is None or self.root.value == value:
            return self.root, self._set_root
        child = self.root
        while True:
            node = child
            smaller = value < child.value
            child = child.left if smaller else child.right
            if child is None or child.value == value:
                return child, node._set_left if smaller else node._set_right

---

How can I improve the speed/efficiency?

Don't spend effort there before measurements suggesting it's a bottleneck.

---

Guide-line for easy-to-use types: Don't make me think.

You define inorder() to print the values in order.
Wouldn't it be cute to be able to use, for a tree ascending
for item in ascending: …? While it was possible to not touch Node, add

    def __iter__(self):
        """ Yield each node in the tree rooted here in order. """
        if self.left is not None:
            yield from self.left
        yield self.value
        if self.right is not None:
            yield from self.right

there, and in the tree

    def __iter__(self):
        """ Yield each node in the tree in order. """
        if self.root is not None:
            yield from self.root

, enabling print(*ascending)