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)

• Toby Speight: Why it felt right to omit the docstrings: you don't need a docstring for __str__, because everybody knows the expected behaviour; and for is_leaf, I think the name provides all the documentation necessary!