Binary Search Tree in Python

A data structure is an efficient way to store and organize data with associated operations in order to take advantage as long as possible it. There are several data structures and, among them, this article will address one in particular: the binary search tree.

First of all, a tree is an abstraction used to stand for non-linear hierarchical structures. There are several types of trees such as: binary tree, AVL tree, red-black tree, B-tree, and so on.

A binary tree is a special type of tree in which each node can have zero, one, or at most two subtrees: the left and right subtrees. If the one doesn’t have any subtrees, it’s a leaf node.

Binary trees are very useful for modeling situations in which at each point in the process, it’s needs to take a decision between two directions.

There are three types of binary trees: strictly binary, full and complete; and they tell apart from each other by node’s the number of subtrees and by the node’s position in the tree.

Strictly binary: it’s the one in which the node always has or none (in the case of a leaf node) or two subtrees, that is, there is no internal node with only one child, all always have two.

Nearly complete: A nearly complete binary tree is a tree in which the height difference between the subtrees of any node is at most 1. In other words, each leaf node in the tree must be at either D or D-1.

Complete: it's a strictly binary tree in which all its leaf nodes are at the same level. In this type of tree, it’s possible to calculate the number of nodes per level, as well as the tree’s node total number.

Implementation Types

Generally, in the implementation a binary tree, there are two commonly used approaches:

• Using an array (static allocation).
• Using a linked list (dynamic allocation).

Which implementation to choose depends exclusively on the application and there is no one that is better than other one in all cases. Now, regardless of the type of implementation used, the following basic operations are possible:

• Tree creation.
• Insertion of an element.
• Removal of an element.
• Search for an element.
• Tree destruction.
• Obtaining information about the tree.

Introduced a little what trees are, now let’s go to the tree that is the title of this article. A binary search tree is a binary tree, therefore, it’s the same properties as a binary tree with the addition that each node has a value (key) associated with it in such a way that the value determines its position in the tree, that is, nodes is the left subtree have a numerical value lower than the root node (or parent node) and all nodes in the right subtree have a numerical value greater than the root node.

Node insertion and removal operations in the binary search tree must be performed respecting this node placement rule. It’s a great alternative to using arrays for binary search operations and has a dynamic structure.

The following are the costs associated with the main operations on a binary search tree containing N nodes. The worst case takes place when the tree isn’t balanced, that is, its height isn’t the minimum possible.

• Insertion: in the average case, O(log N) and in the worst case O(N).
• Removal: in the average case, O(log N) and in the worst case O(N).
• Search: in the average case, O(log N) and in the worst case O(N).

The following is a Python implementation of a binary search tree and its associated operations.

from typing import Union


class Node:

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

    def show(self) -> None:
        print(self.value)

class BinarySearchTree:

    def __init__(self):
        self.root = None
        self.links = []

    def insert(self, value) -> None:

        node = Node(value)

        if not self.root:
            self.root = node
        else:
            current = self.root
            while True:
                parent_node = current

                if value < current.value:
                    current = current.left
                    if not current:
                        parent_node.left = node
                        self.links.append(str(parent_node.value) + '->' + str(node.value))
                        return
                else:
                    current = current.right
                    if not current:
                        parent_node.right = node
                        self.links.append(str(parent_node.value) + '->' + str(node.value))
                        return

    def search(self, value) -> Union[Node, None]:
        current_node = self.root
        while current_node.value != value:
            if value < current_node.value:
                current_node = current_node.left
            else:
                current_node = current_node.right
            if not current_node:
                return None
        return current_node

    # Root, lelf and right
    def pre_order(self, node: Node) -> None:

        if node:
            print(node.value)
            self.pre_order(node.left)
            self.pre_order(node.right)

    # Left, root, right
    def in_order(self, node: Node) -> None:
        if node:
            self.in_order(node.left)
            print(node.value)
            self.in_order(node.right)

    # Left, right, root
    def pos_order(self, node: Node) -> Union[None, bool]:
        if node:
            self.pos_order(node.left)
            self.pos_order(node.right)
            print(node.value)

    def delete(self, value) -> None:
        if not self.root:
            print('The tree is empty...')
            return None

        current_node = self.root
        parent_node = self.root
        _left = True

        while current_node.value != value:
            parent_node = current_node

            if value < current_node.value:
                _left = True
                current_node = current_node.left
            else:
                _left = False
                current_node = current_node.right
            if not current_node:
                return False

        if not current_node.left and not current_node.right:
            if current_node == self.root:
                self.root = None
            elif _left:
                self.links.remove(str(parent_node.value) + '->' + str(current_node.value))
                parent_node.left = None
            else:
                self.links.remove(str(parent_node.value) + '->' + str(current_node.value))
                parent_node.right = None
        elif not current_node.right:
            self.links.remove(str(parent_node.value) + '->' + str(current_node.value))
            self.links.remove(str(current_node.value) + '->' + str(current_node.left.value))

            if current_node == self.root:
                self.root = current_node.left
                self.links.append(str(self.root.value) + '->' + str(current_node.left.value))

            elif _left:
                parent_node.left = current_node.left
                self.links.append(str(parent_node.value) + '->' + str(current_node.left.value))
            else:
                parent_node.right = current_node.left
                self.links.append(str(parent_node.value) + '->' + str(current_node.left.value))

        elif not current_node.left:

            self.links.remove(str(parent_node.value) + '->' + str(current_node.value))
            self.links.remove(str(current_node.value) + '->' + str(current_node.right.value))

            if current_node == self.root:

                self.links.append(str(self.root.value) + '->' + str(current_node.right.value))
                self.root = current_node.right

            elif _left:

                self.links.append(str(parent_node.value) + '->' + str(current_node.right.value))
                parent_node.left = current_node.right

            else:

                self.links.append(str(parent_node.value) + '->' + str(current_node.right.value))
                parent_node.right = current_node.right
        else:

            next = self.get_next(current_node)

            self.links.remove(str(parent_node.value) + '->' + str(current_node.value))
            self.links.remove(str(current_node.right.value) + '->' + str(next.value))
            self.links.remove(str(current_node.value) + '->' + str(current_node.left.value))
            self.links.remove(str(current_node.value) + '->' + str(current_node.right.value))

            if current_node == self.root:

                self.links.append(str(self.root.value) + '->' + str(next.value))     
                self.root = next

            elif _left:

                self.links.append(str(parent_node.value) + '->' + str(next.value))

                parent_node.left = next

            else:

                self.links.append(str(parent_node.value) + '->' + str(next.value))
                parent_node.right = next

            self.links.append(str(next.value) + '->' + str(current_node.left.value))
            self.links.append(str(next.value) + '->' + str(current_node.right.value))

            next.left = current_node.left

        return True

    def get_next(self, node: Node):
        next_parent = node
        next = node
        current = node.right
        while current != None:
            next_parent = next
            next = current
            current = current.left
        if next != node.right:
            next_parent.left = next.right
            next.right = node.right
        return next


if __name__ == "__main__":

    tree = BinarySearchTree()
    tree.insert(53)
    tree.insert(30)
    tree.insert(14)
    tree.insert(39)
    tree.insert(9)
    tree.insert(23)
    tree.insert(34)
    tree.insert(49)
    tree.insert(72)
    tree.insert(61)
    tree.insert(84)
    tree.insert(79)

    tree.pre_order(tree.root)
    print('----------------')
    tree.in_order(tree.root)
    print('----------------')
    tree.pos_order(tree.root)

    print('----------------')

    if tree.search(79):
        print('Found value!')
    else:
        print('Not found value!')

There are many other data structures out there, worth looking into and learning more. The data structure presented here is just some of them. Well, that 's it! See you guys. 👋👨‍💻