Infinite loop when replacing a node in an unsorted tree

Question

I'm doing a homework assignment in Java where I have to create an unsorted binary tree with a String as the data value. I then have to write a function that replaces a Node and any duplicate Nodes that match an old description with a new object that contains a new description.

Here is the code that I am working with, including the test case that causes an infinite loop:

public class Node {

 private String desc;
 private Node leftNode = null;
 private Node rightNode = null;
 private int height;

 public Node(String desc) {
   this.desc = desc;
   height = 0; // assumes that a leaf node has a height of 0
 }

 public String getDesc() {
  return desc;
 }

 public Node getLeftNode() {
  return leftNode;
 }

 public Node getRightNode() {
  return rightNode;
 }

 public void setLeftNode(Node node) {
   ++height;
   leftNode = node;
 }

 public void setRightNode(Node node) {
   ++height;
   rightNode = node;
 }

 public int getHeight() {
   return height;
 }

 public int addNode(Node node) {
   if(leftNode == null) {
     setLeftNode(node);
     return 1;
   }
   if(rightNode == null) {
     setRightNode(node);
     return 1;
   }
   if(leftNode.getHeight() <= rightNode.getHeight()) {
     leftNode.addNode(node);
     ++height;
   } else {
     rightNode.addNode(node);
     ++height;
   }
   return 0;
 }

 public static void displayTree(Node root) {
   if(root != null) {
     displayTree(root.getLeftNode());
     System.out.println(root.getDesc());
     displayTree(root.getRightNode());
   }
 }

 public static Node findNode(Node current, String desc) {
   Node result = null;
   if(current == null) {
     return null;
   }
   if(current.getDesc().equals(desc)) {
     return current;
   }
   if(current.getLeftNode() != null) {
     result = findNode(current.getLeftNode(), desc);
   }
   if(result == null) {
     result = findNode(current.getRightNode(), desc);
   }
   return result;
 }

 public static void replaceNode(Node root, String oldDesc, String newDesc) {
   if(oldDesc == null || newDesc == null) {
     System.out.println("Invalid string entered");
     return;
   }
   boolean replacedAllNodes = false;
   while(replacedAllNodes == false) {
     Node replace = findNode(root, oldDesc);
     if(replace == null) { // No more nodes to replace
       replacedAllNodes = true;
       return;
     }
     replace = new Node(newDesc);
     root.addNode(replace);
   }
   return;
 }


 public static void main(String[] args) {
     Node root = new Node("test1");
     Node test_2 = new Node("test2");
     Node test_3 = new Node("test3");
     Node test_4 = new Node("test4");
     Node test_5 = new Node("test5");
     Node test_6 = new Node("test6");

     root.addNode(test_2);
     root.addNode(test_3);
     root.addNode(test_4);
     root.addNode(test_5);
     root.addNode(test_6);

     displayTree(root);
     replaceNode(root, "test4", "hey");
     System.out.println("-------");
     displayTree(root);
  }
}

After testing the findNode method, and seeing that it returns the correct object, I realized that the infinite loop was being caused by my replaceNode method. I'm just not really sure how it is causing it.

I got it to work with one case by removing the while loop, but obviously that won't work for duplicates, so I'm wondering how I could remove the node with oldDesc and replace it with a new object that contains newDesc when there could be multiple objects with matching oldDesc data.

Answer 1

you are never changing root or oldDesc in your while loop

 while(replacedAllNodes == false) {
     Node replace = findNode(root, oldDesc);
     if(replace == null) { // No more nodes to replace
       replacedAllNodes = true;
       return;
  }
 replace = new Node(newDesc);
 root.addNode(replace);
}

If you watch

public static Node findNode(Node current, String desc) {
   Node result = null;
   if(current == null) {
     return null;
   }
   if(current.getDesc().equals(desc)) {
     return current;
   }
   if(current.getLeftNode() != null) {
     result = findNode(current.getLeftNode(), desc);
   }
   if(result == null) {
     result = findNode(current.getRightNode(), desc);
   }
   return result;
 }

If the if(current.getDesc().equals(desc)) condition matches, replace will always be root so you are stuck in your while loop

Update:

• If you dont necessarily have to replace the whole node, you could just update the description for your node at the end of your while loop.

instead of

 replace = new Node(newDesc);
 root.addNode(replace);

do something like:

  root.setDesc(newDesc);

(of course you would have to create a setDesc() method first)

• If you have to replace the whole object, you have to go like this:

Instead of

replace = new Node(newDesc);
root.addNode(replace);

do something like this:

replace = new Node(newDesc);
replace.setLeftNode(root.getLeftNode);
replace.setRightNode(root.getRightNode);

Plus you have to link the node that pointed to root so it points to replace like one of the following examples (depends on which side your root was of course):

 nodeThatPointedToRoot.setLeftNode(replace);
 nodeThatPointedToRoot.setRightNode(replace);

Answer 2

well looking at your code, you are not replacing a node you are just adding a new node to the edge of the tree and the old node would still be there so the loop will go forever and you can add a temp variable with an auto increment feature and to indicate the level of the node you are reaching to replace and you'll find it's just doing it again and again, instead of doing all this process how about just replacing the description inside that node ?