Skip to main content
Lesson 36 - Deletion from a Binary Tree
Lesson MenuPreviousNext
  
Deletion from a Binary Tree page 2 of 5

  1. Deleting a node involves two steps:

    1. Locating the node to be deleted.
    2. Eliminate that node from the data structure.

  2. After locating the node to be deleted, we must determine the nature of that node.

    1. If it is a leaf, make the parent node point to null.
    2. If it has one child on the right, make the parent node point to the right child
    3. If it has one child on the left, make the parent node point to the left child.
    4. If it has two children, the problem becomes much harder to solve.

    Diagram 36-1

  3. A leaf node containing the value 43 will be easy to delete. The parent node of the node containing 43 will change its right pointer to null.

  4. A node with one child on the right, like the node with value 10, will involve rerouting the node from its parent to its single right child.

  5. But rerouting around the node with value 29, a node with two children, involves breaking off subtrees and reattaching them at the proper location.

  6. The code to implement deletion from a binary tree is given in Handout, H.A.36.1, Deletion from a Binary Tree. The recursive deleteHelper method that locates the node to be deleted is given below:

    public void delete(Comparable target)
    {
        myRoot = deleteHelper(myRoot, target);
    }
    
    private TreeNode deleteHelper(TreeNode node, Comparable target)
    {
      if (node == null)
      {
        throw new NoSuchElementException();
      }
      else if (target.equals(node.getValue()))
      {
         return deleteTargetNode(node);
      }
      else if (target.compareTo(node.getValue()) < 0)
      {
        node.setLeft(deleteHelper(node.getLeft(), target));
        return node;
      }
      else //target.compareTo(root.getValue()) > 0
      {
        node.setRight(deleteHelper(node.getRight(), target));
        return node;
      }
    }
  7. After the value to be deleted is input in testDelete, this method calls the delete method of the BinarySearchTree object the first time and passes a reference to the Item object containing the id value to be deleted from the tree. The delete method then passes the root of the tree (myRoot) and the target item to be located to the deleteHelper method. The deleteHelper method receives a TreeNode reference alias (node). The deleteHelper method has 4 scenarios:

    1. node == null, the value does not exist in the tree, throw a NoSuchElementException.
    2. We found the correct node (target.equals(node.getValue())), call deleteTargetNode and pass it node.
    3. Did not find the node yet, recursively call deleteHelper and pass it the internal reference to the left child.
    4. Recursively call deleteHelper and pass it the internal reference to the right child.


Lesson MenuPreviousNext
Contact
 ©ICT 2003, All Rights Reserved.