Tree is a type of DataStructure, consisting mainly of nodes. Every node has some child node until we
reach the last node having no childrens. Those last nodes are called leaf nodes. The topmost node is
called the root node.
Coming to the binary tree, it is a special type of tree where every node has maximum of two childrens.
Also see : How to install selenium in python
Table of Contents
How to Implement binary search tree python 3.8
In binary search tree(BST) every left child of any particular node has a value less than its parent, and
every right child of any particular node has a value more than its parent.
Coming to initialization of node, we start by making a node class in python consisting of a left and right
node.
class bt:
def __init__(self, data):
self.data = data
self.left = None
self.right = NoneIn this way we create a node with blank left and right node and data field which contains the value of
node.
Coming to insertion of element, there are two types of BST, one with duplicate entries and one where
duplicate elements are not allowed.
Also see : Matrix multiplication in python
def insertelem(node,data):
if node.data == data:
return 0
if node.data<data:
if not node.right:
node.right = bt(data)
else:
insertelem(node.right,data)
elif node.data>data:
if not node.left:
node.left = bt(data)
else:
insertelem(node.left,data)
In this way of insertion no duplicates are allowed.
def insertelem(node,data):
if node.data<data:
if not node.right:
node.right = bt(data)
else:
insertelem(node.right,data)
else:
if not node.left:
node.left = bt(data)
else:
insertelem(node.left,data)
here duplicates are allowed.
Coming to essence of binary search tree, it is quite popular for its efficiency of finding element. Here as
we know left child of a node is smaller than its parent and right child is greater.
We can use this information in our favour.
def find(node, num):
if node:
if node.data == num:
return node
elif node.data < num:
return find(node.right , num)
else:
return find(node.left, num)Three Step to Implement binary search tree python 3.8
This is a recursive approach of finding an element. This has these steps
Step 1: check if node’s value is equal to the number we want to find, if yes return the value.
Step 2: if node’s value is less than element’s value then we perform search on its right child.
Step 3: if node’s value is more than element’s value then we perform search on its left child.
This is how we perform search operation on a binary tree. It has a time complexity of logN.
Coming to deletion of element in a binary tree, it’s a bit complex than other steps. For deletion
operation we use recursive approach.
Also see : Attributes in python
These are some basic operation which we perform on BST.
def delt(root,node):
if not node:
return
if root.left is node:
if root.left.left:
root.left = root.left.left
return
elif root.left.right:
root.left = root.left.right
return
else:
root.left = None
return
if root.right is node:
if root.right.left:
root.right = root.right.left
elif root.right.right:
root.right = root.right.right
else:
root.right = None
return
if root.left and root.left.data < node.data:
delt(root.right,node)
elif root.right and root.right.data > node.data:
delt(root.left,node)Summary :
In this article we saw Python Program to Construct and Implement binary search tree python 3.8 so about this section you have any query then free to ask me
Name of Intern who share this Task :
swapnil raj
