Binary Search Tree Implementation

binary-search-tree-python-implementationBinary 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

Binary-Search-Tree
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
binary-search-tree-capital-cities
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?

    binary-search-tree-random-numbers
    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:

    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:

  • saveToFile() – Save the whole content of the binary tree in a text file. You will have to investigate the best format to do so. For instance you could save the BST data structure as a JSON file or an XML file.
  • loadFromFile() – Load the whole content of the binary tree from a text file (using the JSON or XML formats).
  • Share Button
    Tagged with: