Python program to insert an element into binary search tree














































Python program to insert an element into binary search tree



#Python program to insert an element into binary search tree


What are Binary Search Trees?

Binary Search trees are the special category of the tree that follows a predefined property of mapping the elements within the tree. This predefined property is that, in a Binary Search tree, all the elements that are smaller than the parent node are inserted at the left and all the elements greater than the parent node are inserted at the right as demonstrated in the figure below.

The properties that separates a binary search tree from a regular binary tree is

  1. All nodes of left subtree are less than root node
  2. All nodes of right subtree are more than root node
  3. Both subtrees of each node are also BSTs  i.e. they have the above two properties

A tree having a right subtree with one value smaller than the root is shown to demonstrate that it is not a valid binary search tree

The binary tree on the right isn't a binary search tree because the right subtree of the node "3" contains a value smaller that it.


Insert  a value in Binary Search Tree(BST)

Whenever an element is to be inserted, first locate its proper location. Start searching from the root node, then if the data is less than the key value, search for the empty location in the left subtree and insert the data. Otherwise, search for the empty location in the right subtree and insert the data.


Algorithm:

if root is None:
   root=node
else:
   if root.value<node.value:
      if root.right is None:
         root.right=node
      else:
         insert(root.right,node)
   else:
      if root.left is None:
         root.left = node
      else:
         insert(root.left,node)


code:
# Python program to demonstrate insert operation in binary search tree

class Node:
	def __init__(self,key):
		self.left = None
		self.right = None
		self.value = key

# A function to insert a new node with the given key value
def insert(root,node):
	if root is None:
		root=node
	else:
		if root.value<node.value:
			if root.right is None:
				root.right=node
			else:
				insert(root.right,node)
		else:
			if root.left is None:
				root.left = node
			else:
				insert(root.left,node)

# A function for inorder tree traversal
def inorder(root):
	if root:
		inorder(root.left)
		print(root.value)
		inorder(root.right)




root=Node(9)
insert(root,Node(5))
insert(root,Node(2))
insert(root,Node(4))
insert(root,Node(11))
inorder(root)

Output:
2
4
5
9
11


Time Complexity:
In worst case, we may have to travel from root to the deepest leaf node.
The worst case time complexity of insertion operation is O(h) 
where h is height of Binary Search Tree.

More Articles of yashwanth gudigamolla:

Name Views Likes
Python SciPy stats.skew() function 1588 17
Python Scipy Stats 1167 14
Python SciPy stats beta() function 2029 14
Python Scipy Special (List of Different Functions) 1548 15
Python SciPy Integration 1409 12
Python Scipy Fourier Transforms(scipy.fftpack) 1462 17
Python Scipy linalg 1316 13
Python SciPy stats.expon() function 2287 17
Python SciPy stats.chi() function 993 24
Python Scipy Multidimentional image processing (scipy.ndimage) 1618 26
SciPy - ODR 1485 23
Python SciPy stats.cosine() function 958 14
Python SciPy stats.trim1() function 1051 11
Python SciPy stats.tvar() function 1107 16
Python SciPy stats.tvar() function 1046 23
SciPy - Basic Functionality 1152 27
Python SciPy stats.betaprime() function 1006 13
Python Scipy CSGraph 1204 19
Python Scipy File Input and Output (IO) 1616 20
Python Scipy Optimize 1444 23
Python Scipy Special package (scipy.special) 1107 25
Python SciPy stats.tsem() function 949 12
Python SciPy stats.variation() function 1386 16
Python SciPy stats.tsem() function 998 14
SciPy - Spatial 1179 25
Python program to insert an element into binary search tree 9696 29
Python SciPy stats.chi2() function 1905 18
Python SciPy Interpolation 6649 21
C++ program to find inorder predecessor and successor for a given key in binary search tree with recursion 2477 15
python program to check if two trees are identical using recursion 1192 12
Python SciPy constants 2014 18
Python SciPy stats.sem() function 1338 22
Python Scipy Introduction 1684 26
Python SciPy stats alpha() function 1170 23
SciPy - Cluster 1285 20

Comments