A binary tree is a widely-asked topic in coding contests and interviews. There are various concepts related to binary trees, like different ways to traverse a binary tree, the left, and right view, etc.

The dstructure package is a Python library for data structures and algorithms. In this post, we'll look at how to use Python's dstructure module to create a binary tree and execute various operations on it.

Installation

Open a terminal and type the following command to install dstructure library:

pip install dstructure

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Binary Tree

Binary Trees represent non-linear data structures that have the following properties:

One node is marked as the Root node.

Every node other than the root is associated with one parent node.

Each node has the following attributes:

Data or key

Left child pointer

Right child pointer

A binary tree is defined as a tree with no more than two children. Because each element in a binary tree can only have two children, they are commonly referred to as the left and right children. The dstructure library, on the other hand, aids in the direct implementation of a binary tree.

Methods Available

Python’s dstructure module provides multiple functions to deal with binary trees. In this section, we will look at those sections and use them to operate our binary tree. We'll create the Binary Search Tree first, then apply all of the procedures.

To make a binary tree, first import the dstructure module, then build a BTree class object to start with an empty binary tree and insert nodes using the insert() method. The insert method creates a Binary Search Tree.

The methods for creating and performing various operations on a binary tree are listed below.

‘insert’ function

‘inorder’ function

‘preorder’ function

‘postorder’ function

‘get_bfs’ function

‘left_view’ function

‘right_view’ function

‘total_nodes’ function

‘insert’ function

insert(int_value): This function takes an integer as input and inserts the integer into the binary tree. The insert function is the standard insert function used to create a binary search tree. It does not insert the nodes in the level-order fashion.

Implementation

# import module.
from dstructure.BTree import BTree
# create an object of the BTree class.
tree_obj=BTree(15)
# inserts the following values into the Binary Tree represented by obj.
tree_obj.insert(18)
tree_obj.insert(12)
tree_obj.insert(14)
tree_obj.insert(10)
tree_obj.insert(16)
# print the binary tree
print(tree_obj)

Output

<dstructure.BTree.BTree object at 0x7f4278326f90>

‘in order’ function

inorder(obj): This function takes a BTree class object and returns the inorder traversal of the tree. As you can guess, the in-order traversal of a binary search tree generates a sorted list.

Implementation

# inorder_array holds the values in the inorder traversal of the tree obj inorder_array = tree_obj.inorder(tree_obj) print(inorder_array)

Output

[10, 12, 14, 15, 16, 18]

‘preorder’ function

preorder(obj): This function takes a BTree class object and returns the preorder traversal of the tree.

Implementation

# inorder_array holds the values in the preorder traversal of the tree obj preorder_array = tree_obj.preorder(tree_obj) print(preorder_array)

Output

[15, 12, 10, 14, 18, 16]

‘postorder’ function

postorder(obj): This function takes a BTree class object and returns the postorder traversal of the tree.

Implementation

# postorder_array holds the values in the postorder traversal of the tree obj postorder_array = tree_obj.postorder(tree_obj) print(postorder_array)

Output

[10, 14, 12, 16, 18, 15]

‘get_bfs’ function

get_bfs() : This function returns the bfs (breadth-first traversal) traversal of the tree.

Implementation

# return Breadth First Search of tree in list. bfs_tree = tree_obj.get_bfs() print(bfs_tree)

Output

[15, 18, 12, 16, 14, 10]

‘left_view’ function

left_view(): This function returns the left view of the tree.

Implementation

# returns the left view of the tree in the left_tree variable. left_tree = tree_obj.left_view() print(left_tree)

Output

[15, 12, 10]

‘right_view’ function

right_view() : This function returns the right view of the tree.

Implementation

# returns the right view of the tree in the right_tree variable. right_tree = tree_obj.right_view() print(right_tree)

Output

[15, 18, 16]

‘total_nodes’ function

total_nodes(): This function returns an integer representing the total number of nodes in the tree.

Implementation

# return the number of nodes present in the tree_obj. count_tree = tree_obj.total_nodes() print(count_tree)

What is the time complexity of the insertion of an element in a binary search tree?

The worst-case time complexity for the insertion of an element in a BST is O(logN) where N is the size of the data set.

Conclusion

In this blog, we discussed the implementation of binary tree data structure in Python using the dstructure library. We also explored various helper/utility functions to operate on the binary tree object, like for example, inorder, preorder and postorder functions to print the inorder, preorder and postorder traversals of the tree, etc. Binary trees are widely known in the world of programming and networks. We saw how to traverse the binary tree created using the functions defined in the dstrucutre library. There are many more functions to explore in the dstructure library.

Hence learning never stops, and there is a lot more to learn.