Data Structures (BCA) 3rd Sem Previous Year Solved Question Paper 2022

Algorithms to insert and search for a value in a binary search tree (BST):

Algorithm InsertBST(root, value):
    if root is null:
        # Create a new node with the given value
        new_node = CreateNode(value)
        return new_node
    else if value < root.value:
        # Recursively insert into the left subtree
        root.left = InsertBST(root.left, value)
    else:
        # Recursively insert into the right subtree
        root.right = InsertBST(root.right, value)
    return root

    • Start at the root of the BST.
    • If the root is null, create a new node with the given value and return it.
    • If the value is less than the current node's value, recursively insert into the left subtree.
    • If the value is greater than or equal to the current node's value, recursively insert into the right subtree.
    • Return the modified tree.

Algorithm to Search in a Binary Search Tree (BST)

Algorithm SearchBST(root, value):
    if root is null or root.value is equal to value:
        return root
    else if value < root.value:
        # Recursively search in the left subtree
        return SearchBST(root.left, value)
    else:
        # Recursively search in the right subtree
        return SearchBST(root.right, value)

    • Start at the root of the BST.
    • If the root is null or its value is equal to the target value, return the current root (found the value).
    • If the target value is less than the current node's value, recursively search in the left subtree.
    • If the target value is greater than the current node's value, recursively search in the right subtree.

example of using these algorithms to insert and search in a binary search tree:

# Create an empty BST
root = null

# Insert values into the BST
root = InsertBST(root, 50)
root = InsertBST(root, 30)
root = InsertBST(root, 70)
root = InsertBST(root, 20)
root = InsertBST(root, 40)
root = InsertBST(root, 60)
root = InsertBST(root, 80)

# Search for a value
result = SearchBST(root, 40)
# If result is not null, the value is found in the tree

These algorithms allow you to efficiently insert and search for values in a binary search tree, which is a data structure that maintains the properties of a BST with elements on the left being smaller and elements on the right being larger.