I've had a go, and it works for the left subtree but not the right.
I'm close but my logic is wrong, can anyone help correct and explain the logic to this.
public static MyNode preOrderNumbering(MyNode n) {
if (n != null) {
n.obj = 0; // Set root decoration to 0;
preOrderHelper(n, 1); // Set decorations according to preorder.
}
return n;
}
public static MyNode preOrderHelper(MyNode n, int counter) {
if (n != null) {
if (n.left != null) {
n.left.obj = counter++; // Set the left object decoration to current count + 1;
preOrderHelper(n.left, counter);
}
if (n.right != null) {
n.right.obj = counter++; // Set the left object decoration to current count + 1;
preOrderHelper(n.right, counter);
}
}
return n;
}
Before:
After:
You need to update the counter
with everything that's discovered on the left
before going to the right
.
Something like this:
public static int preOrderNumbering(MyNode n, int count){
if(n != null){
n.obj = ++count;
count = preOrderNumbering(n.left, count);
count = preOrderNumbering(n.right, count);
}
return count;
}