Binary Search Tree

Before attempting to understand my implementation of the BST, be sure to read the chapter in A Common Sense Guide to Data Structures and Algorithms by Jay Wengrow. It explains why we need such a data structure and helps us understand it better.

Tip

I kid you not, the book makes it fun!

Binary Search Tree Implementation in Python
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
"""Binary Search Tree Implementation in Python"""


class BSTException(Exception):
    """This exception is raised when a particular facet or requirement
    of a BST is not satisfied."""


class BinarySearchTreeNode:
    """A Single node of a Binary Search Tree"""

    def __init__(self, value, left=None, right=None):
        self.value = value
        if left is not None:
            if left > self.value:
                raise BSTException(
                    "The left value should be lesser than the current value.")
        self.left = left
        if right is not None:
            if right < self.value:
                raise BSTException(
                    "The right value should be greater than the current value.")
        self.right = right

    def __eq__(self, other):
        return self.value == other.value

    def __lt__(self, other):
        return self.value < other.value

    def __le__(self, other):
        return self.value <= other.value

    def __gt__(self, other):
        return self.value > other.value

    def __ge__(self, other):
        return self.value >= other.value


def construct_binary_search_tree(*args):
    """Given a list of integers, this can construct a BST and returns the root
    node."""
    if len(args) == 0:
        return
    elif len(args) > 0:
        root_node = BinarySearchTreeNode(args[0])
        if len(args) > 1:
            for value in args:
                insert_into_bst(value, root_node)
        return root_node


def search_bst(search_value, node):
    """Finds a value in a BST given a node

    To find a node in a BST, remember:

    1. Each node has a maximum of 2 children (a left and a right).
    2. The left side of a node has values lesser than the node.
    3. The right side of a node has values greater than the node.
    """
    if node is None or node.value == search_value:
        return node
    elif search_value < node:
        return search_bst(search_value, node.left)
    else:
        return search_bst(search_value, node.right)


def insert_into_bst(value, node):
    """Inserts a value into a Binary Search Tree
    1. If the value to be inserted is less than the current node, it belongs on
    the left.
    2. If the value to be inserted is greater than the current node, it belongs
    on the right.

    Remember, all nodes have only a maximum of 2 children: a left child and a
    right child.
    """
    if value < node:
        if node.left is None:
            node.left = BinarySearchTreeNode(value)
        else:
            insert_into_bst(value, node.left)
    elif value > node:
        if node.right is None:
            node.right = BinarySearchTreeNode(value)
        else:
            insert_into_bst(value, node.right)


def delete_from_bst(value, node):
    """Deletes a value from a BST
    When deleting remember the following:

    1. If the node being deleted has no children, then simply delete it.
    2. If the node being deleted has one child, delete the node and plug the
    child into the spot where the deleted node was.
    3. When deleting a node with two children, replace the deleted node with
    the successor node. The successor node is the child node whose value is
    the least of all values that are greater than the deleted node.
    4. To find the successor node: visit the right child of the deleted value,
    and then keep on visiting the left child of each subsequent child until
    there are no more left children. The bottom value is the successor node.
    5. If the successor node has a right child, after plugging the successor
    node into the spot of the deleted node, take the former right child of the
    successor node and turn it into the left child of the former parent of the
    successor node.
    """
    if node is None:
        return None
    elif value < node:
        node.left = delete_from_bst(value, node.left)
        return node
    elif value > node:
        if node.left is None:
            return node.right
        elif node.right is None:
            return node.left
        else:
            node.right = lift_node_in_bst(node.right, node)
            return node


def lift_node_in_bst(node, node_to_delete):
    """If the current node of this function has a left child, recursively call
    this function to continue down the left subtree to find the successor node.
    """
    if node.left is not None:
        node.left = lift_node_in_bst(node.left, node_to_delete)
        return node
    else:
        node_to_delete.value = node.value
        return node.right


def traverse_bst_and_run_function(node, function, mode="in-order"):
    """Traverses a bst and runs a function on each value.
    The modes are 'in-order', 'pre-order', 'post-order'
    TODO: Try to implement *returning* the values accrued
    by these function calls.
    """

    if node is None:
        return
    if mode == "in-order":
        traverse_bst_and_run_function(node.left, function)
        function(node)
        traverse_bst_and_run_function(node.right, function)
    elif mode == "pre-order":
        function(node)
        traverse_bst_and_run_function(node.left, function)
        traverse_bst_and_run_function(node.right, function)
    elif mode == "post-order":
        traverse_bst_and_run_function(node.left, function)
        traverse_bst_and_run_function(node.right, function)
        function(node)