Binary Search Tree

My Linh Tran
3 min readJan 25, 2021
Photo by Niklas Veenhuis on Unsplash

A Tree is one of the most commonly used data structures among others.

“ A data structure that stimulates the hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes. “

Souce: Wikipedia

The topic of today is Binary Tree. So a binary tree has a similar structure to a general tree but a parent node of a binary tree has no more than two children. This makes operations like inserting a new element or searching for a value in the tree become less complicated.

Geeksforgeeks.org clarifies the difference between a general tree and a binary tree as followed.

Source: GeeksforGeeks

For better visualizing of how searching, inserting or deleting a node in a binary tree works, visit cs.usfca.edu. Let’s break it down.

Step 1: Initiate a Node object with class type Node.

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

A tree data structure can be defined recursively as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the “children”), with the constraints that no reference is duplicated, and none points to the root. “
- Source: Wikipedia -

An object of class type Node will have a value and references to its left and right nodes. Since the initial node still hasn’t got any left or right references yet, its value would be None.

Step 2: Initiate an object of type BST.

class BST(object):
def __init__(self, root):
self.root = Node(root)

Here we are assigning an object of type Node to the attribute root of the object of type BST. So now the root of BST will also have a value and references to its left and right nodes.

Step 3: Create a function to insert a new element/node into the tree.

To do this, we need at least 2 functions, one for official usage and another one as a helper.

def _insert(self, node, new_val):
if node is not None:
if node.value > new_val:
if node.left is not None:
self._insert(node.left, new_val)
else:
node.left = Node(new_val)
else:
if node.right is not None:
self._insert(node.right, new_val)
else:
node.right = Node(new_val)
else:
node = Node(new_val)

As much as we love convention, “_insert” is a convention that is used for functions that are not supposed to be called by users.

The simplifier recursive algorithm for this function would be as followed:

  • If there is a node available then look at it, if not create a new node.
  • If a node is available, compare it with the value to be inserted new_val:
  • If the value of the node is bigger than new_val and the node on the left is available, call the function again. If it is not available, create a new node.
  • If the value of the node is smaller or equal to new_val and the node on the right is available, call the function again. If it is not available, create a new node.

Note:

  • Since we only modify the tree, we don’t need to return anything.
  • When moving to a new node, start the function again.
  • The function called in the recursive algorithm is a method of the same object of type BST. Do not forget to put “self” in it. There is a great explanation of how “self” works in python pythontips.com.

Exercise:

  • Create another function on how to search for a value in the BST.

--

--