Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Understanding
2.
Installation
3.
Binary Tree
3.1.
Methods Available
4.
‘insert’ function
4.1.
Implementation
5.
‘in order’ function
5.1.
Implementation
6.
‘preorder’ function
6.1.
Implementation
7.
‘postorder’ function
7.1.
Implementation
8.
‘get_bfs’ function
8.1.
Implementation
9.
‘left_view’ function
9.1.
Implementation
10.
‘right_view’ function
10.1.
Implementation
11.
‘total_nodes’ function
11.1.
Implementation
12.
Frequently Asked Questions
12.1.
What is the time complexity of the insertion of an element in a binary search tree?
13.
Conclusion
Last Updated: Mar 27, 2024

Binary Tree using dstructure library in Python

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Understanding

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: 

  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)

Output

<dstructure.BTree.BTree object at 0x7f4278326f90>

 

illustration image

‘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)

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:

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!

Previous article
Types of Binary trees
Next article
Height of a Binary Tree
Live masterclass