Question

PYTHON CODING

Create a method for the Binary Search Tree (deleteNode) that deletes a specified node identified by its value, and rearranges the descendants of the deleted node to ensure the resulting Tree meets the requirements of a Binary Search Tree.

a) Discuss and justify your approach to address each possible case.

b) Is the new tree (with the deleted node removed) unique? Discuss your answer.

Discuss method's Big-O notation. Add proper and consistent documentation to identify code sections or lines to clearly identify its purpose.

Illustrate the performance of the deleteNode method. For the BST of datalist delete 71, 400, 271 938, and 69 from the tree in the same order. For all illustrated examples, enumerate the trees (before and after deletion) using your orderTraversal and justify the correctness of your delete method

Answer 1

Discuss and justify your approach to address each possible case.

BST Deletion

Delete function is used to delete the specified node from a binary search tree. However, we must delete a node from a binary search tree in such a way, that the property of binary search tree doesn't violate. There are three situations of deleting a node from binary search tree.

The node to be deleted is a leaf node

It is the simplest case, in this case, replace the leaf node with the NULL and simple free the allocated space.

In the following image, we are deleting the node 85, since the node is a leaf node, therefore the node will be replaced with NULL and allocated space will be freed.

fig

The node to be deleted has only one child.

In this case, replace the node with its child and delete the child node, which now contains the value which is to be deleted. Simply replace it with the NULL and free the allocated space.

In the following image, the node 12 is to be deleted. It has only one child. The node will be replaced with its child node and the replaced node 12 (which is now leaf node) will simply be deleted.

fig

The node to be deleted has two children.

It is a bit complexed case compare to other two cases. However, the node which is to be deleted, is replaced with its in-order successor or predecessor recursively until the node value (to be deleted) is placed on the leaf of the tree. After the procedure, replace the node with NULL and free the allocated space.

In the following image, the node 50 is to be deleted which is the root node of the tree. The in-order traversal of the tree given below.

6, 25, 30, 50, 52, 60, 70, 75.

replace 50 with its in-order successor 52. Now, 50 will be moved to the leaf of the tree, which will simply be deleted.

fig

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

b) Is the new tree (with the deleted node removed) unique? Discuss your answer.

Discuss method's Big-O notation. Add proper and consistent documentation to identify code sections or lines to clearly identify its purpose.

yes the new tree with the deleted nod removed is unique.

For deleting a Node there are three scenarios possible..

1. Node is a leaf node: This is a simple case, figure out whether this node is left or right node of parent and set null as child for the parent for that side.
2. Node is having one child: Establish a direct link between parent node and child node of this node.
3. Node has two children: This is little tricky.. the steps involved in this are.
   1. First find the successor (or predecessor) of the this node.
   2. Delete the successor (or predecessor) from the tree.
   3. Replace the node to be deleted with the successor (or predecessor)

Before knowing the concept of deletion, we should understand the concept of successor and predecessors

Successor: In a binary tree successor of a node is the smallest node of the tree that is strictly greater then this node.

There are two possible cases with a node

• A node has right children: In this case the leftmost child of the right sub-tree will be successor.

• A node has no children: Go to the parent node and find a node for which this node is part of left sub-tree.

Discuss method's Big-O notation.

• Deletion: For deletion of element 1, we have to traverse all elements to find 1 (in order 3, 2, 1). Therefore, deletion in binary tree has worst case complexity of O(n). In general, time complexity is O(h).

The worst case time complexity for search, insert and delete operations in a general Binary Search Tree is O(n)..

Add proper and consistent documentation to identify code sections or lines to clearly identify its purpose

Algorithm

Delete (TREE, ITEM)

• Step 1: IF TREE = NULL
     Write "item not found in the tree" ELSE IF ITEM < TREE -> DATA
  Delete(TREE->LEFT, ITEM)
  ELSE IF ITEM > TREE -> DATA
     Delete(TREE -> RIGHT, ITEM)
  ELSE IF TREE -> LEFT AND TREE -> RIGHT
  SET TEMP = findLargestNode(TREE -> LEFT)
  SET TREE -> DATA = TEMP -> DATA
     Delete(TREE -> LEFT, TEMP -> DATA)
  ELSE
     SET TEMP = TREE
     IF TREE -> LEFT = NULL AND TREE -> RIGHT = NULL
     SET TREE = NULL
  ELSE IF TREE -> LEFT != NULL
  SET TREE = TREE -> LEFT
  ELSE
      SET TREE = TREE -> RIGHT
  [END OF IF]
  FREE TEMP
  [END OF IF]
• Step 2: END

Illustrate the performance of the deleteNode method. For the BST of datalist delete 71, 400, 271 938, and 69 from the tree in the same order. For all illustrated examples, enumerate the trees (before and after deletion) using your orderTraversal and justify the correctness of your delete method​​​​​​​

# Python program to demonstrate delete operation
# in binary search tree

# A Binary Tree Node
class Node:

   # Constructor to create a new node
   def __init__(self, key):
       self.key = key
       self.left = None
       self.right = None

# A utility function to do inorder traversal of BST
def inorder(root):
   if root is not None:
       inorder(root.left)
       print root.key,
       inorder(root.right)

# A utility function to insert a new node with given key in BST
def insert( node, key):

   # If the tree is empty, return a new node
   if node is None:
       return Node(key)

   # Otherwise recur down the tree
   if key < node.key:
       node.left = insert(node.left, key)
   else:
       node.right = insert(node.right, key)

   # return the (unchanged) node pointer
   return node

# Given a non-empty binary search tree, return the node
# with minum key value found in that tree. Note that the
# entire tree does not need to be searched
def minValueNode( node):
   current = node

   # loop down to find the leftmost leaf
   while(current.left is not None):
       current = current.left

   return current

# Given a binary search tree and a key, this function
# delete the key and returns the new root
def deleteNode(root, key):

   # Base Case
   if root is None:
       return root

   # If the key to be deleted is smaller than the root's
   # key then it lies in left subtree
   if key < root.key:
       root.left = deleteNode(root.left, key)

   # If the kye to be delete is greater than the root's key
   # then it lies in right subtree
   elif(key > root.key):
       root.right = deleteNode(root.right, key)

   # If key is same as root's key, then this is the node
   # to be deleted
   else:
      
       # Node with only one child or no child
       if root.left is None :
           temp = root.right
           root = None
           return temp
          
       elif root.right is None :
           temp = root.left
           root = None
           return temp

       # Node with two children: Get the inorder successor
       # (smallest in the right subtree)
       temp = minValueNode(root.right)

       # Copy the inorder successor's content to this node
       root.key = temp.key

       # Delete the inorder successor
       root.right = deleteNode(root.right , temp.key)

   return root

for illustration run this code in python and insert binary tree containing 71, 400, 271 938, 69 and other values then delete it as above mentioned.​​​​​​​For all illustrated examples, enumerate the trees (before and after deletion) using your orderTraversal and justify the correctness of your delete method