Binary Tree using dstructure library in Python

Binary Tree

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

1. One node is marked as the Root node.
2. Every node other than the root is associated with one parent node.
3. Each node has the following attributes:
   1. Data or key
   2. Left child pointer
   3. 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.

1. ‘insert’ function
2. ‘inorder’ function
3. ‘preorder’ function
4. ‘postorder’ function
5. ‘get_bfs’ function
6. ‘left_view’ function
7. ‘right_view’ function
8. ‘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)

You can also try this code with Online Python Compiler

Run Code

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

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

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

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

Output

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

‘left_view’ function

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

Implementation

Output

[15, 12, 10]

‘right_view’ function

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

Implementation

Output

[15, 18, 16]

‘total_nodes’ function

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

Implementation

Output

6

Check out this problem - Mirror A Binary Tree

Frequently Asked Questions

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.

Recommended Problems:

• Binary Tree Postorder Traversal
• Inorder Traversal
• Preorder Traversal
• Postorder Traversal
• Left view of a Binary Tree

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!