# Binary Search Tree (BST) Implementation

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


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()
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
"""
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()?

    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)

• 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! Oct 25, 2021 at 8:22