Why Is My Binary Search Tree Delete Recursion Not Ending?

I am trying to implement a binary search tree using Java. One of the functions that I want to create is the delete function. This will consists of two methods, one called delete and the other called getNodeToDelete. The getNodeToDelete method is a helper function for the delete method.

The getNodeToDelete method is recursive, and basically returns the node that the user wants to delete from the tree. Using the node that is returned from this getNodeToDelete method, the non-recursive delete method basically makes important decisions on how to delete this node depending on different cases (e.g. is it a leaf node, is it a root node etc.).

This is the non-recursive delete method:

 /**       * Deletes the relevant node (according to the key inputted by the user), using two helper functions:       * getNodeToDelete(int deleteKey, Node root) and getMinRight(Node nodeToDelete).       * @param key       */      public void delete(int key) {          if (root.left == null && root.right == null) {              if (root.key == key) {                  root = null;                  System.out.println("It reached the first if-statement of the delete() method.");              }          }          Node nodeToDelete = getNodeToDelete(key, root); //The node that is returned from its helper function.          System.out.println("This is the node to delete: " + nodeToDelete.key);          if (nodeToDelete.right == null && nodeToDelete.left == null) {  //If the nodeToDelete is a leaf.              nodeToDelete = null;  //            System.out.println("This is the key of the deleted node: " + nodeToDelete.key);              return;          } else if (nodeToDelete.right == null) {  //If the nodeToDelete has an empty right tree.              Node immediateLeftNode = nodeToDelete.left;              nodeToDelete.key = immediateLeftNode.key;              nodeToDelete.left = immediateLeftNode.left;              nodeToDelete.right = immediateLeftNode.right;          } else if (nodeToDelete.right != null) {  //If the nodeToDelete has a non-empty right tree              if (nodeToDelete.right.left == null) {  //If the left branch of the right branch of nodeToDelete is empty.                  nodeToDelete.key = nodeToDelete.right.key;                  nodeToDelete.right = nodeToDelete.right.right;              } else {                  Node replacementNode = getMinRight(nodeToDelete);                  nodeToDelete.key = replacementNode.key;              }          }      }  

And this is the recursive getNodeToDelete method:

/**       * Assumption: the key does exist in the tree.       * Returns the node that the user wants to delete, based on the key that the user inputs.       * @param deleteKey       * @param startingRoot       * @return       */      public Node getNodeToDelete(int deleteKey, Node startingRoot) {          if (startingRoot == null) {              return null;          }            if (startingRoot.key == deleteKey) {              return startingRoot;          }            if (deleteKey < startingRoot.key) {              getNodeToDelete(deleteKey, startingRoot.left);          }            getNodeToDelete(deleteKey, startingRoot.right);          return startingRoot;      }  

The problem is, the helper function, getNodeToDelete, traverses down the tree to one of its nodes, for example, the leaf node of value -12. Then it returns that node, but the recursive method getNodeToDelete seems to not end. It then traverses back up to the root node again, always resulting in the returned value being the root node.

I know that there are many different approaches to implementing a binary search tree in Java, but this recursion problem is bothering me and I really want to know the reason behind the failure of this.

Please let me know if you need more clarification. Thanks

https://stackoverflow.com/questions/66467563/why-is-my-binary-search-tree-delete-recursion-not-ending March 04, 2021 at 10:06AM