5062CEM

Programming and Algorithms 2

Building a Binary Search Tree

 Light  Dark  Auto

Building a Binary Search Tree

For this activity, you will need to be using an Integrated Development Environment (IDE). The recommended IDE for this module is JetBrains IntelliJ IDEA for Python and JetBrains CLion for C++. You can follow instructions at the following page to set up your development environment:

Setting up your Development Environment

For this task you need to implement a node class and will be used to store pointers to the relevant child nodes for that parent node. The node itself should also hold the value (or data) that is associated with the parent node. This can be either a numeric or string value.

For this task you need to implement a function that will enable the user to insert a new node into the BST. When the node is inserted, it should be appended as a leaf node in the correct spot.

In the example below, the user is concerned with inserting the value 7 into the binary search tree. The function should traverse through the BST and find the suitable location to append the new node. In this instance, it would be on the right hand-side of parent node 6.

Before Insertion
After Insertion

For this task, you are required from the pseudocode given below to create two search methods for a Binary Search Tree (BST), one iterative and the other recursive.

The iterative method will be called find_i(), whilst the recursive method will be called find_r(). The find_r() method will need a sub_method called _find_r(). Each of these methods should return True, False or None.

Note, that the solution for None is not given in the iterative pseudocode.

FIND_I(tree, target)
    cur_node ← tree.root
    WHILE cur_node != 0
        IF cur_node.value = target
            RETURN cur_node (or TRUE)(or cur_node.value)
        ELSE IF cur_node.value > target
            cur_node ← cur_node.left
        ELSE
            cur_node ← cur_node.right
    RETURN FALSE

FIND_R(tree, target)
    IF tree.root
        IF tree._FIND_R(target, tree.root)
            RETURN True
        RETURN False
    ELSE
        RETURN None

_FIND_R(target, cur_node)
   IF target > cur_node.data AND cur_node.right
       RETURN tree._FIND_R(target, cur_node.right)
   ELSE IF target < cur_node.data AND cur_node.left
       RETURN tree._FIND_R(target, cur_node.left)
   IF target == cur_node.data
       RETURN True

For this task you are required to implement an iterative method called remove which deletes a node and reorganises the tree using the pseudocode provided below. There a hints included where the pseudocode is missing.

Implement your solution and ensure that the remove method works correctly, i.e. not only is the node deleted, but the tree is also correctly re-organised. Add comments to your code to show your understanding.

REMOVE(tree, target)
    IF tree.root IS None
        RETURN False
    ELSE IF tree.root.data = 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
            delNodeParent ← tree.root
            delNode ← tree.root.right
            WHILE delNode.left
                delNodeParent ← delNode
                delNode = delNode.left
            tree.root.data ← delNode.data
            IF delNode.right
                IF delNodeParent.data > delNode.data
                    delNodeParent.left ← delNode.right
                ELSE IF delNodeParent.data < delNode.data
                    delNodeParent.right ← delNode.right
            ELSE
                IF delNode.data < delNodeParent.data
                    delNodeParent.left ← None
                ELSE
                    delNodeParent.right ← None

    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

    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

    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

    // NOT IMPLEMENTED                                  //CASE 4: Target has right child only

    ELSE                                                //CASE 5: Target has left and right children
        delNodeParent ← node
        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 IF delNodeParent < delNode.data
                delNodeParent.right ← delNode.right

        ELSE
            IF delNode.data < delNodeParent.data
                delNodeParent.left ← None
            ELSE
                delNodeParent.right ← None

Task 5: Visualising a Tree

For this task you will implement a function that will display the BST in the terminal window. You may want to consider printing the tree in a method that looks like the following:

      1
    /   \
   2     3
  / \   / \
 4   5 6   7

If you are struggling with this lab activity, you may want to get some additional support. You can speak to the module leader/team in the room of when the lab week is active, or you can visit the Additional Support page for more information on how you can get extra support.