algorithms

A catalog of data structures and problems with approaches to solve them

View the Project on GitHub gitgik/algorithms

BST implementation

A node is said to be a BST node if and only if it satisfies the BST property:

The BST should support insertion, searching and removal of values. The removal method should only remove the first instance of the target value.

class BST:
    """
    We'll use the iterative approach (due to constant space).
    Recursive approach creates a call stack in memory -> O(n) space.
    """

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

    def insert(self, value):
        """Average Case: O(log(N)) time | O(1) space
        Worst Case: (Where the tree is unbalanced 
        and has only one branch to the left)
            O(n) time, where n = number of nodes in the tree
            O(1) space
        """
        current_node = self
        while True:
            if value < current_node.value:
                if current_node.left is None:
                    current_node.left = BST(value)
                    break
                else:
                    current_node = current_node.left
            else:
                # value is greater than current node's value
                if current_node.right is None:
                    current_node.right = BST(value)
                    break
                else:
                    current_node = current_node.right
        return self

    def contains(self, value):
        """Average Case: O(log(N)) time |  O(1) space
        Worst Case: O(n) time | O(1) space
        """
        current_node = self
        while current_node is not None:
            if value < current_node.value:
                current_node = current_node.left
            elif value > current_node.value:
                current_node = current_node.right
            else:
                # found it!
                return True
        return False

    def remove(self, value, parent_node=None):
        """Average Case: O(log(N)) time | O(1) space
        Worst Case: O(n) time, O(1) space
        """
        current_node = self
        while current_node is not None:
            if value < current_node.value:
                parent_node = current_node
                current_node = current_node.left
            elif value > current_node.value:
                parent_node = current_node
                current_node = current_node.right
            else:
                # we've found the node, time to delete it
                if current_node.left is not None and current_node.right is not None:
                    # set current node value = smallest value of right subtree.
                    current_node.value = current_node.right.get_min_value()
                    current_node.right.remove(current_node.value, current_node)
                elif parent_node is None:
                    # if we are removing the root node (it does not have a parent node)
                    if current_node.left is not None:
                        current_node.value = current_node.left.value
                        current_node.right = current_node.left.right
                        current_node.left = current_node.left.left
                    elif current_node.right is not None:
                        current_node.value = current_node.right.value
                        current_node.left = current_node.right.left
                        current_node.right = current_node.right.right
                    else:
                        # no child nodes exist for this BST, so do nothing
                        pass
                elif parent_node.left == current_node:
                    parent_node.left = (
                        current_node.left if current_node.left is not None else
                        current_node.right)
                elif parent_node.right == current_node:
                    parent_node.right = (
                        current_node.left if current_node.left is not None else
                        current_node.right)
                break
        return self

    def get_min_value(self):
        """Finds the smallest value in a sub-tree."""
        current_node = self
        while current_node.left is not None:
            current_node = current_node.left
        return current_node.value
bst = BST(10).insert(5).insert(15).insert(
        7).insert(2).insert(14).insert(22)

bst.contains(22)
True