C++ Java Electronics Physics Astronomy Robotics Summer Other Courses

Adding and Deleting Nodes

Example 1: Deleting a leaf or a node with only one child

   The 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.  
  
Deleting 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 left child.

Example 2: Deleting a node with 2 children and left child has no right - node 75, for example

   Copy the contents of the left child of target and set it as the current value. target.setValue(target.getLeft().getValue()).
   As shown above, the value 75 is replaced with 62.
   Reattach the left subtree to maintain an ordered tree.
   The left subtree of the node reference by
target will now point to the node containing the value 58. target.setLeft(target.getLeft().getLeft()).
   As shown above, since the node that originally contained the value 62 is no longer referenced, it is removed (garbage collected).

Example 3: Deleting the root node

   Position marker to access the node with the largest value in the left subtree. This is the rightmost node in the left subtree.   
   TreeNode marker = target.getLeft();   while (marker.getRight().getRight() != null
)     marker = marker.getRight().
   As shown above, marker now references the node pointing to the node with largest value in the left subtree (43). 
   Copy the contents of the right child of
marker and set it as the current value.    target.setValue(marker.getRight().getValue())
   As shown above, the value 52 is replaced with 43.
   Delete the largest value from the right subtree. Reattach the right subtree to maintain an ordered tree.
    marker.setRight(marker.getRight().getLeft())
   As shown above, the node containing the value 43 is no longer referenced.