Reading Time: 7 Minutes

This post is part-2 of this data structures series, which will focus on exploring binary trees in depth and finally demonstrating the logic with python code.

In this series of exploring abstract data types we will be diving into concepts like trees, graph traversals, stack, queue, linked list, hash tables etc in python programming language. This series requires you to have a basic understanding of python programming, concepts of class, object oriented programming, functions and scope, data types such as array, list, tuple, strings, integers, dictionary etc.

For those who are beginners into the world of programming, and have explored the basic data types, assume that all the use cases and requirements related to data can be performed using them. Even I had the same mindset when I started to learn data structures, I was able to handle data of any volume and complexity with the basic data types such as list and dictionary.

But then when I started diving deep into the world of data structures, I began to understand the different aspects of it and how they can help to formulate complex relationships between data and overall improve code efficiency when we are dealing with large and complex data.

What is a Binary Tree?

A binary tree is a hierarchical data structure composed of nodes, where each node contains a value and at most two child nodes, referred to as the left child and the right child.

The upper most node in a binary tree is known as the root and the nodes which doesn’t have a child node or at the bottom most are known as leaf. The nodes in the tree are connected by edges.

The characteristic that makes a normal tree structure as a binary tree is that each node can have, at most, two children, and these children are arranged in a specific order.

The left child of a node holds a value less than or equal to the parent’s value, while the right child holds a value greater than the parent’s value. This ordering property ensures that binary trees can be used in applications that require efficient searching, insertion, and deletion operations.

Speaking of applications, binary trees find widespread applications in file systems, where the hierarchical structure represents the order of directories and files, it has a remark in gaming space, where the decisions between the players are made, etc.

To boil it down, they offer a versatile and efficient way to organise and manage hierarchical relationships within data.

Now, lets look at an example where we will construct a binary tree with the given inputs, lets say we have been given with the following data→ 100, 50, 150, 25, 75, 65, 200
1. Inserting 100 and 50:

2. Inserting 150 and 25:

3. Inserting 75 and 65:

4. Inserting 200 and 125:

I have generated this tree using https://www.cs.usfca.edu/~galles/visualization/BST.html, do check out the website and solve some other binary tree based insertion to get a complete idea of what’s happening.

Now, lets get into the coding part and design a class that will be able to generate a binary tree.

The Source Code

Note: General binary trees allows duplicate values, but here we will restrict duplicate values and design a binary search tree.

1. First we create a class named bin_search_tree and define the important variables that will be used to construct the tree.

class bin_search_tree:
    def __init__(self, root):
        self.left_child = None
        self.root = root # the key will be initialised as root node
        self.right_child = None

2. Now in order to construct a binary tree, by paper we are basically thinking in iteration and inserting the data into the tree until all the nodes are inserted. Similarly in here also, we use iterations and recursively call the insert function to get the job done, it will make more sense once you go through the code.

def insert(self, data):
      """
      print("Current node: ")
      print("----------------------------------------")
      print(self.left_child, "|", self.root, "|", self.right_child)
      print("----------------------------------------")
      print(self.root, "->", data)
      """
      if self.root is None:
          self.root = data
          return

      if self.root == data:  # this line removes duplicate values
          return

      if self.root > data:
          if self.left_child is not None:  # it checks whether left_child is empty
              self.left_child.insert(data) # if no, then it recursively calls the insert method with the left_child as root node
          else:
              # now self.left_child is None and ready to take elements
              self.left_child = bin_search_tree(data)

			# if the data is found to be greater than root, then the node is inserted as right child. The same logic is followed to insert right nodes
      else:
          if self.right_child is not None:
              self.right_child.insert(data)
          else:
              self.right_child = bin_search_tree(data)

You can run the code with print statements that are commented to get a deeper understanding of how objects are created and values are assigned.

This is a small section of the printed output by running this code→

root = bin_search_tree(None)

lst = [100, 50, 150, 25, 75, 65, 200, 125]
for _ in lst:
    root.insert(_)

Current layer:

None | None | None

None -> 100

Current layer:

None | 100 | None

100 -> 50

Current layer:

<main.bin_search_tree object at 0x7fb2e00cd070> | 100 | None

100 -> 150

Current layer:

<main.bin_search_tree object at 0x7fb2e00cd070> | 100 | <main.bin_search_tree object at 0x7fb2e00c7fd0>

100 -> 25

Current layer:

None | 50 | None

50 -> 25

Current layer:

<main.bin_search_tree object at 0x7fb2e00cd070> | 100 | <main.bin_search_tree object at 0x7fb2e00c7fd0>

100 -> 75

3. Once we have created the tree successfully, we also need to view the tree, we can’t print the objects and node values as we have printed above, there needs to be a common ground for interpretation.

For that there are 3 basic universal ways of traversing a tree, they are:

• In-order traversal – the tree is traversed in the order of left, root, right.
• Pre-order traversal – the tree is traversed in the order of root, left, right.
• Post-order traversal – the tree is traversed in the order of left, right, root.
  
  Now lets look at the coding section.

def preorder(self):
		print(self.key, end=" ") # the root node

    if self.left_child is not None:
        self.left_child.preorder() # left child 

    if self.right_child is not None:
        self.right_child.preorder() # right child

def inorder(self):
		if self.left_child is not None: # left child 
        self.left_child.inorder()

    print(self.key, end=" ") # the root node

    if self.right_child is not None: # right child
        self.right_child.inorder()

def postorder(self):
		if self.left_child is not None: # left child 
        self.left_child.postorder()

    if self.right_child is not None: # right child
        self.right_child.postorder()

    print(self.key, end=" ") # the root node

That was the coding part to construct and traverse a binary tree, do run this code using a new sample piece of data, and I highly recommend you to design a search and delete function, I can assure you that if you have completely understood the recursion part in insert method, it will be very easy for you to design the search and delete function.

There are a lot of classifications when it comes to the types of binary trees, such as full binary trees, degenerate binary tree, each serve a unique purpose and can be adapted according to the needs of the project, but they all follow the basic thumb rule of insertion, which is inserting nodes with smaller value than the root node to the left and the greater value to the right.

As mentioned in the beginning, binary Trees has a huge space for applications in the realm of computer science. If you are into data science or machine learning, you would have likely come across decision tree algorithms, random forest, etc, where understanding tree based data structures are crucial.

If you would like to explore the real world application of a decision tree with python code and understand the logic behind it, check out my post in the data science and programming section or click the link here to directly go to the post.

Thank you for reading all along, your curiosity and engagement are highly valued, do drop your feedbacks or queries in the comment section below. Subscribe to sapiencespace and enable notifications to get regular insights.

Click here to view similar insights.