I'm having some trouble with Binary Trees in java. The assignment wants me to build a binary tree and then create functions to return the next node in preorder, postorder, and inorder. So here is my attempt;
public class BinaryTree {
Node root;
private Node addR(Node c, int x) {
if (c == null) {
return new Node(x);
}
if (x < c.value) {
c.left = addR(c.left, x);
}
else if (x > c.value) {
c.right = addR(c.right, x);
}
else {
return c;
}
return c;
}
public void add(int x) {
root = addR(root, x);
}
public Node preorderNext(Node n) {
if (n.left != null) {
System.out.println(n.left.value);
return n.left;
}
else if (n.right != null) {
System.out.println(n.right.value);
return n.right;
}
else {
System.out.println("Empty");
return null;
}
}
public Node postorderNext(Node root, Node n) {
if (n == root) {
System.out.println("Empty");
return null;
}
Node parent = n.parent;
if(parent.right == null || parent.right == n) {
System.out.println(parent.value);
return parent;
}
Node c = parent.right;
while (c.left != null) {
System.out.println(c.left);
c = c.left;
}
System.out.println(c.value);
return c;
}
public Node inorderNext(Node root, Node n) {
if (n.right != null) {
System.out.println(n.right.value);
return minValue(n.right);
}
Node p = n.parent;
while (p != null && n == p.right) {
n=p;
p=p.parent;
}
System.out.println(p.value);
return p;
}
Node minValue(Node n) {
Node c = n;
while (c.left != null) {
c = c.left;
}
return c;
}
public Node searchR(Node c, int x) {
if(c==null) {
return null;
}
if (x==c.value) {
return c;
}
if (x<c.value) {
c.left = searchR(c.right, x);
}
c.right = searchR(c.right, x);
return c;
}
}
And here is my main;
public static void main(String[] args) {
BinaryTree test = new BinaryTree();
test.add(7);
test.add(5);
test.add(6);
test.add(9);
test.add(3);
test.add(8);
test.preorderNext(test.searchR(test.root, 5));
test.postorderNext(test.root, test.searchR(test.root, 5));
test.inorderNext(test.root, test.searchR(test.root, 5));
}
}
So the code works as far as nothing crashes, but it returns the wrong nodes. I double checked to make sure the searchR method was returning the right value, and it was, but the other functions simply return the wrong numbers. Anyone have any guidance on where I'm going wrong? I'm a little lost since it's not actually an error and clearly an issue within my code. I also can't use collections in this problem, but I don't think that would be relevant here anyway.
Your searchR function is screwing up the tree due to the c.right and c.left assignments. You're very close, though.
After all the add calls are complete, your tree looks like this:
7
/ \
5 9
/ \ /
3 6 8
When you call searchR(test.root, 5), your tree winds up looking like this**:
7
/ \
9 9
As you can see, not only is this not a valid binary tree, but many of the nodes are missing, and the node with a value of 9 was duplicated.
Get rid of the assignments, wrap the .right traversal in an else block, get rid of the final return statement, and you'll be good to go:
public Node search(Node node, int target) {
if (node == null) return null;
if (node.value == target) {
return node;
} else if (target < node.value) {
return search(node.left, target);
} else {
return search(node.right, target);
}
}
Your preorderNext looks OK.
Your postorderNext looks almost OK. The issue is that I don't see you setting up the .parent members of the Nodes, so your postorderNext function will always crash with a NullPointerException at the parent.right == null || parent.right == n conditional check.
Your inorderNext will break for the same reason; no parent members are set up. My recommendation would be to add a parameter to your add function to hold the parent node. Then, when you return new Node(x), you can also set the parent member appropriately. Note that you should pass c as the parent node in each recursive call.
** If you're curious how I figured out the exact nature of the tree after your searchR function, I threw a handful of print statements into the searchR function and ran it myself. This was the result:
Starting recursive call for node 1933863327 and x = 5
5 < 7, doing c.left = searchR(c.right, x)
Starting recursive call for node 146589023 and x = 5
5 < 9, doing c.left = searchR(c.right, x)
c == null, returning null
Recursive call for c.left returned, c.left.value = null
Doing c.right = searchR(c.right, 5)
c == null, returning null
Recursive call for c.right returned, c.right.value = null
Ending recursive call for node 146589023 and x = 5
c.value = 9
Recursive call for c.left returned, c.left.value = 9
Doing c.right = searchR(c.right, 5)
Starting recursive call for node 146589023 and x = 5
5 < 9, doing c.left = searchR(c.right, x)
c == null, returning null
Recursive call for c.left returned, c.left.value = null
Doing c.right = searchR(c.right, 5)
c == null, returning null
Recursive call for c.right returned, c.right.value = null
Ending recursive call for node 146589023 and x = 5
c.value = 9
Recursive call for c.right returned, c.right.value = 9
Ending recursive call for node 1933863327 and x = 5
c.value = 7