Binary Search Tree Implementation

Binary Search Trees are an effective solution to store data in a computer program and perform a binary search.

The benefits of using a BST (Binary Search Tree) data structure is that data can be added to the tree as it is received and the BST structure will store it effectively so that:

• A sorted list of the data can be generated using an in-order traversal of the tree.
• A binary search can be easily implemented making this data structure very effective to access/search through. A binary search has an O(log(n)) notation for time complexity.
• Data/Nodes can easily be added or removed from the tree without having to rearrange the whole data structure

The characteristics of a Binary Search Tree are as follows:

1. Being a type of tree data structure, it consists of nodes and branches with a parent/child relationship between nodes,
2. Each node can have a maximum of two children node: The left child and the right child,
3. The left subtree of a node contains only nodes with values lesser than the node’s value.
4. The right subtree of a node contains only nodes with values greater than the node’s value.

When a new node is added to the tree, if added in a way that do not conflict with the 4 characteristics listed above.

Capital Cities BSTRandom Numbers BST

Can you add the following cities to this Binary Search Tree:

Cape Town

Seoul

How would you then remove New-York from this BST tree?

Can you add the following numbers to this Binary Search Tree:

62

59

23

How would you then remove number 28 from this BST tree?

Depth-first Traversal Of Binary Search Tree

The three depth-first traversal methods to read through all the nodes of a BST are:

1. Pre-order Traversal
2. In-order Traversal
3. Post-order Traversal

The in-order traversal is frequently used as it retrieves the nodes in order: alphabetical order or numerical order depending on the data types of the nodes’ values. This remains the case even if the nodes were added to the tree in a completely different order.

You can read more and practise your understanding of the different breadth-first and depth-first traversals of tree on this blog post as well as investigate their algorithms (in pseudocode).

Python Implementation

Different approaches can be used to implement a Binary Search Tree in Pythons. It can be achieved by combining different data structures (e.g. hash tables and lists). However in this blog post we will implement our BST data structure using Object Oriented concepts (OOP Programming).

First we will create a Node class to store the following 3 values:

• The value of the node,
• A pointer to the left node,
• A pointer to the right node.

Here is the Python code for the Node class:

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

We will then create a Tree class.
The main property of our Tree class will be its root Node. We will then implement a range of methods as follows:

• insert() – Insert a new value/node in the correct position within the BST,
• delete() – Find a node based on its value and remove it from the tree,
• find() – Perform a Binary Search on the tree to find a specific Node based on its value,
• preorder_traversal() – Perform and output the result of a pre-order traversal of the tree,
• inorder_traversal() – Perform and output the result of an in-order traversal of the tree,
• postorder_traversal() – Perform and output the result of a post-order traversal of the tree,
• draw() – Perform and output the result of a post-order traversal of the tree.

You can investigate the Python code used to implement all of the above 7 methods in the trinket below.

Python Code

Use the following Python code to build your own BST, adding one value at a time. You will be able to visualise your tree on screen and view the outputs of the three depth-first traversal methods:

Python Challenge

Add two methods to the Tree class as follows: