# 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

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
return
else:
current = current.right
if not current:
parent_node.right = node
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:
parent_node.left = None
else:
parent_node.right = None
elif not current_node.right:

if current_node == self.root:
self.root = current_node.left

elif _left:
parent_node.left = current_node.left
else:
parent_node.right = current_node.left

elif not current_node.left:

if current_node == self.root:

self.root = current_node.right

elif _left:

parent_node.left = current_node.right

else:

parent_node.right = current_node.right
else:

next = self.get_next(current_node)

if current_node == self.root:

self.root = next

elif _left:

parent_node.left = next

else:

parent_node.right = next

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: