 Python Program to Construct and Implement binary search tree python 3.8

## Python Program to Construct and Implement binary search tree python 3.8

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

### 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 = None``````

In 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&lt;data:

if not node.right:

node.right = bt(data)

else:

insertelem(node.right,data)

elif node.data&gt;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&lt;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 &lt; 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 &lt; node.data:

delt(root.right,node)

elif root.right and root.right.data &gt; node.data:

delt(root.left,node)``````

Summary :