Question : Java Binary Tree Logical Errors

I include here the code for a binary tree. There are several problems with the code. The tree is empty at first, then values are inserted. The first value will be at the top. The next value will be on the first values left side if it is smaller then the first value. It will be placed on the right side if it is larger then the initial value. This value will be the first values child node, and the first value will be its parent. When a value has both a left and a right child node, those nodes again will create new child nodes by the same logic when new values are inserted in the tree. In this example I will use the values 1 3 4 10 12 13 14 15 16 20 21 28 29 30 39. I will then delete value 10, and see if I can re-arrange the tree correctly. The initial tree is supposed to look like as in figure A.

1) When I delete the node with value 10 I follow the logic displayed in figure B. Everything seems to work OK, and all the numbers that remain are displayed, but when searching for all the values, the mechanism seems to report that some of the numbers are missing. Just after listing them in order. Example:

"The tree in a sorted display: 1 3 4 14 12 13 15 16 20 21 28 29 30 39
Is 3 in the tree: true
Is 4 in the tree: true
Is 1 in the tree: true
Is 10 in the tree: false
Is 12 in the tree: false
Is 13 in the tree: false
Is 14 in the tree: true
Is 16 in the tree: true
Is 20 in the tree: true
Is 21 in the tree: true
Is 28 in the tree: true
Is 29 in the tree: true
Is 30 in the tree: true
Is 39 in the tree: true"

This happens only when deleting 10(left side child node), but not 28(right side child node).

2) The order of the numbers seems to get juggled around after deletion. I have not been able to figure out why. After deleting node with value 10, I get this order: 1 3 4 14 12 13 15 16 20 21 28 29 30 39
Here you can see that 14 is placed wrong. This does not happen when deleting node with value 28.

Figure A:
 
FigA.png (21 KB) (File Type Details) 
Figure A
323583
 


Figure B:
 
FigB.png (27 KB) (File Type Details) 
Figure B
323584
 


When deleting right side nodes:
We start by simulating deletion of 28.
A) 29 takes 28's place.
B) We ask node at 29 to find a new space for 20.

Then we simulate deletion of 10.
I) 14 takes 10's place.
II) We ask 14 to find new space for 3.

The logic is the same in both examples, only handling different sides of a given node(depending on what side the node is on that is being deleted). 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
244:
245:
246:
247:
248:
249:
250:
251:
252:
253:
254:
255:
256:
257:
258:
259:
260:
261:
262:
263:
264:

class SubTree {
  private SubTree rightTree = null;
  private SubTree leftTree = null;
  private SubTree parent = null;
  private int value = 0;

  public SubTree(int value) {
    this.value = value;
  }

  public SubTree(int value, SubTree parent) {
    this.value = value;
    this.parent = parent;
  }

  public void insertValue(int newValue) {
    if (value >= newValue) {
      if (leftTree != null) {
        leftTree.insertValue(newValue);
      } else {
        leftTree = new SubTree(newValue, this);
      }
    } else {
      if (rightTree != null) {
        rightTree.insertValue(newValue);
      } else {
        rightTree = new SubTree(newValue, this);
      }
    }
  }

  public String toString () {
    String returString = "";
    if (leftTree != null) {
      returString = leftTree.toString() + " ";
    }
    returString = returString + value;
    if (rightTree != null) {
      returString = returString + " " + rightTree.toString();
    }
	showObject();
    return returString;
  }

  public boolean lookForValue(int søkeVerdi) {
    if (søkeVerdi == value) {
      return true;
    }
    if (value > søkeVerdi) {
      if (leftTree != null) {
        return leftTree.lookForValue(søkeVerdi);
      } else {
        return false;
      }
    } else {
      if (rightTree != null) {
        return rightTree.lookForValue(søkeVerdi);
      } else {
        return false;
      }
    }
  }
  
  public boolean deleteValue(int value) {
    if (this.value == value) {
	//If we have found node with right value, we have to find if it has any child nodes
	  if ((rightTree == null) && (leftTree == null)) {
	    /**This node has no child, it can be linked off the tree.*/
		if(value <= this.parent.getValue()) { //We are on left side, and we will relink there at the parent
			this.parent.relink(0, null);
		} else { //We are on the right side, and we relink there at the parent
			this.parent.relink(1, null);
		}
		//At the end we relink this objects backreference to parent:
		this.parent = null;
		return true;
	  } else if (((rightTree == null) && (leftTree != null)) || ((rightTree != null) && (leftTree == null))) {
	    /**The node has only one child node. We link over this node to the child */
		if(value <= this.parent.getValue()) { //We are on left side, and we link there over this object to this objects rightTree
			if ((rightTree != null) && (leftTree == null)) this.parent.relink(0, this.rightTree);
			if ((rightTree == null) && (leftTree != null)) this.parent.relink(0, this.leftTree);
			this.rightTree = null;
		} else { //Or else we are on the right side, and we link there over this object to this objects leftTree
			if ((rightTree != null) && (leftTree == null)) this.parent.relink(1, this.rightTree);
			if ((rightTree == null) && (leftTree != null)) this.parent.relink(1, this.leftTree);
			this.leftTree = null;
		}
		//At the end we relink this objects reference to the parent:
		this.parent = null;
		return true;
	  } else {
	    /**The noden has two child nodes, these have to moved correctly and placed correctly under the parent node */
		if(value <= this.parent.getValue()) { //We are on the left side, we link right child node on left side at the parent
			//We then ask the right child node to find new space for the left childnode
			this.parent.relink(0, this.rightTree);
			this.rightTree.giveNewPlace(this.leftTree);
			this.rightTree = null;
			this.leftTree = null;
			this.parent = null;
		} else { //Or else we are on the right side, and we link right child node on the right side at the parent
			this.parent.relink(1, this.rightTree);
			this.rightTree.giveNewPlace(this.leftTree);
			this.rightTree = null;
			this.leftTree = null;
			this.parent = null;
		}
		this.parent = null;
		return true;
	  }
	} else {
	//If we have not foumd the node with the correct value, we will look for the correct child note and look there:
	  if(this.value < value) {
	    if (rightTree != null) rightTree.deleteValue(value);
	  } else {
	    if (leftTree != null) leftTree.deleteValue(value);
	  }
	}
    return false;
  }
  public int getValue() {
    return this.value;
  }
  public void relink(int i, SubTree t) {
    if (i > 0) {
	  this.rightTree = t;
	} else {
	  this.leftTree = t;
	}
	t.setNewParent(this);
  }
  public SubTree getChildNode(int i) {
    if (i > 0) {
	  return this.rightTree;
	} else {
	  return this.leftTree;
	}
  }
  public void giveNewPlace(SubTree t) {
	//Takes SubTree t and tries to give it a new place in the tree
    //Check if this node has space for a left child node, if not:
    //Check if this node has space for a right child node and order the two childnodes correct, if not:
    //Ask the next left childNode to give new place with its giveNewPlace().
	if (this.leftTree == null) {
		this.leftTree = t;
		t.setNewParent(this);
	} else if (this.rightTree == null) {
		if(getValue() < t.getValue()) {
			this.rightTree = t;
			t.setNewParent(this);
		} else {
			this.rightTree = this.leftTree;
			this.leftTree = t;
			t.setNewParent(this);
		}
	} else {
		this.leftTree.giveNewPlace(t);
	}
  }
  public void setNewParent(SubTree t) {
	this.parent = t;
  }
  public void showObject() {
	System.out.println("----------------------------------------");
	if (parent != null) System.out.println("Parent: " + parent.getValue());
    System.out.println("*Value: " + this.value);
    if (rightTree != null) System.out.println("Right child: " + rightTree.getValue());
    if (leftTree != null) System.out.println("Left child: " + leftTree.getValue());
	System.out.println("----------------------------------------");
  }
}

class BinarySeekingTree {
  private SubTree rot;
  public String toString() {
    if (rot != null) {
      return rot.toString();
    } else {
      return null;
    }
  }

  public void insertValue(int value) {
    if (rot != null) {
      rot.insertValue(value);
    } else {
      rot = new SubTree(value, null);
    }
  }
  
  public boolean deleteValue(int value) {
	//If there is no root in the tree, then there is no value to delete
    if (rot == null) {
	  return false;
	} else {
	  if(rot.deleteValue(value)) {
	    return true;
	  } else {
	    return false;
	  }
	}
  }

  public boolean lookForValue(int søkeVerdi) {
    if (rot == null) {
      return false;
    }
    return rot.lookForValue(søkeVerdi);
  }
}

class Seek {
	public static void main(String[] args) {
		BinarySeekingTree tree = new BinarySeekingTree();
		tree.insertValue(15);
		tree.insertValue(10);
		tree.insertValue(28);
		tree.insertValue(3);
		tree.insertValue(14);
		tree.insertValue(20);
		tree.insertValue(29);
		tree.insertValue(1);
		tree.insertValue(4);
		tree.insertValue(12);
		tree.insertValue(13);
		tree.insertValue(16);
		tree.insertValue(21);
		tree.insertValue(30);
		tree.insertValue(39);
		System.out.println("The tree in a sorted display: " + tree.toString()); //Sorting fails after deleting an object
		System.out.println("Is 3 in the tree: " + tree.lookForValue(3));
		System.out.println("Is 4 in the tree: " + tree.lookForValue(4));
		System.out.println("Is 1 in the tree: " + tree.lookForValue(1));
		System.out.println("Is 10 in the tree: " + tree.lookForValue(10));
		System.out.println("Is 12 in the tree: " + tree.lookForValue(12));
		System.out.println("Is 13 in the tree: " + tree.lookForValue(13));
		System.out.println("Is 14 in the tree: " + tree.lookForValue(14));
		System.out.println("Is 16 in the tree: " + tree.lookForValue(16));
		System.out.println("Is 20 in the tree: " + tree.lookForValue(20));
		System.out.println("Is 21 in the tree: " + tree.lookForValue(21));
		System.out.println("Is 28 in the tree: " + tree.lookForValue(28));
		System.out.println("Is 29 in the tree: " + tree.lookForValue(29));
		System.out.println("Is 30 in the tree: " + tree.lookForValue(30));
		System.out.println("Is 39 in the tree: " + tree.lookForValue(39));
		System.out.println("We now try to delete the value 10 from the tree, but not 28.");
		tree.deleteValue(10);
		//tree.deleteValue(28);
		System.out.println("");
	System.out.println("The tree in a sorted display: " + tree.toString()); //Sorting fails after deleting an object
		System.out.println("Is 3 in the tree: " + tree.lookForValue(3));
		System.out.println("Is 4 in the tree: " + tree.lookForValue(4));
		System.out.println("Is 1 in the tree: " + tree.lookForValue(1));
		System.out.println("Is 10 in the tree: " + tree.lookForValue(10));
		System.out.println("Is 12 in the tree: " + tree.lookForValue(12));
		System.out.println("Is 13 in the tree: " + tree.lookForValue(13));
		System.out.println("Is 14 in the tree: " + tree.lookForValue(14));
		System.out.println("Is 16 in the tree: " + tree.lookForValue(16));
		System.out.println("Is 20 in the tree: " + tree.lookForValue(20));
		System.out.println("Is 21 in the tree: " + tree.lookForValue(21));
		System.out.println("Is 28 in the tree: " + tree.lookForValue(28));
		System.out.println("Is 29 in the tree: " + tree.lookForValue(29));
		System.out.println("Is 30 in the tree: " + tree.lookForValue(30));
		System.out.println("Is 39 in the tree: " + tree.lookForValue(39));
	}
}

Answer : Java Binary Tree Logical Errors

Your code would work properly if the tree would remain balanced after deletion. The main cause of your problem is explained below:
Here is the left subtree after you remove the node with value 10.

                                            14
                                           /    \
                                         3      12
                                        /  \        \
                                      1     4       13

If we want to find the node with value 12, according to your code the 12 is compared with 14. If the 12 < 14, the search is done in the left subtree, otherwise in the right one. Obviously, the search return false because the node 12 (as well as the node 13) is located in the right subtree.
To solve the problem you should keep the tree balanced.
Random Solutions  
 
programming4us programming4us