3
\$\begingroup\$

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                
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.