ADV 01 - Remove method for Binary Tree class
Intro
The Remove method for a Binary Tree class deletes a node with a specified value, adjusting the tree structure while preserving its binary search tree property.
Task
From the partial pseudocode given below (one case is omitted), implement an iterative method called remove which deletes a node and reorganises the tree. There are indications where the pseudocode is missing. NB the pseudocode crosses pages. Add comments to show your understanding. Implement your solution into the python Binary Tree class given in pseudo code. Make sure that remove works correctly; that is, not only is the target node deleted, but the tree is also correctly re-organised. If not, it may mean the pseudocode needs some detail adding. You may decide, if you wish, to implement the entire class and solution in C++ instead of, or in addition to, the python solution, but this is not mandatory for this task.
Pseudo-code
REMOVE(tree, target)
IF tree.root IS None //if no tree
RETURN False
ELSE IF tree.root.data = target //if tree root is target
IF tree.root.left IS None AND tree.root.right IS None
tree.root ← None
ELSE IF tree.root.left AND tree.root.right IS None
tree.root ← tree.root.left
ELSE IF tree.root.left IS None AND tree.root.right
tree.root ← tree.root.right
ELSE IF tree.root.left AND tree.root.right
IF_LEFT_AND_RIGHT(tree.root)
//if root is not target
parent ← None
node ← tree.root
WHILE node and node.data != target
parent ← node
IF target < node.data
node ← node.left
ELSE IF target > node.data
node ← node.right
IF node IS None OR node.data != target //CASE 1: Target not found
RETURN False //for info only (we could not find it)
ELSE IF node.left IS None AND node.right IS None //CASE 2: Target has no children
IF target < parent.data
parent.left ← None
ELSE
parent.right ← None
RETURN True //info only
ELSE IF node.left AND node.right IS None //CASE 3: Target has left child only
IF target < parent.data
parent.left ← node.left
ELSE
parent.right ← node.left
RETURN True //info only
NOT IMPLEMENTED //CASE 4: Target has right child only
ELSE //CASE 5: Target has left and right children
IF_LEFT_AND_RIGHT(node)
IF_LEFT_AND_RIGHT(node) //called if delete node whether root or otherwise
delNodeParent ← node //has left and right children
delNode = node.right
WHILE delNode.left
delNodeParent ← delNode
delNode ← delNode.left
node.data ← delNode.data
IF delNode.right
IF delNodeParent.data > delNode.data
delNodeParent.left ← delNode.right
ELSE
delNodeParent.right ← delNode.right
ELSE
IF delNode.data < delNodeParent.data
delNodeParent.left ← None
ELSE
delNodeParent.right ← None