Search Operation on Binary Search Tree

 

Seach operation on binary search tree is same 

as Binary search where array remains sorted.

In here we'll compare our key value with root node. 

If the value of both are not same then we will check 

if the key value is less than the root value or not.

If true we'll go to the left node of the root and do the

same task again(comparing).

If the key value is greater than the root value then

iteration will go to the right node of the root and

do the same task.

Code is here...

class Node:

def __init__(self,data):

self.left = None

self.right = None

self.val = data

# insert a new node with the given value

def insert(root,node):

if root is None:

root = node

else:

if root.val < node.val:

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)

#*********************Search Function******************************

def search_node(root, key):

if(root is None or root.val == key):

return root

if key < root.val:

return search_node(root.left, key)

else:

return search_node(root.right, key)

#-------------------------------------------------------------------

def inorder(root):

if root:

inorder(root.left)

print(root.val, end=' ')

inorder(root.right)

def preorder(root):

if root:

print(root.val, end=' ')

preorder(root.left)

preorder(root.right)

def postorder(root):

if root:

postorder(root.left)

postorder(root.right)

print(root.val, end=' ')

def delete_node(root):

del root

#Create the following BST

# 8

# / \

# 5 15

# / \ / \

# 4 6 11 16

if __name__ == "__main__":

value = int(input("Enter the value of root node: "))

r = Node(value)

while True:

choice = int(input("Do you insert more nodes: (1/0)"))

if(choice!=1):

break

val = int(input("Enter the value: "))

insert(r,Node(val))

# Print inoder traversal of the BST

print("Inorder Traversal is :")

inorder(r)

print("\nPreorder Traversal is :")

preorder(r)

print("\nPostorder Traversal is :")

postorder(r)

#---------------Search Operation-----------------------

key = int(input("Enter the value to be searched: "))

get_val = search_node(r, key)

if get_val is not None:

print("\nThe key value has been founded")

else:

print("Key not found!")

#------------------------------------------------------

#Operation of delete root node so that memory leakage will

    not occur

delete_node(r)

# Code by Rakshit_Coding()