Reputation: 449
I have an assignment and I need some help with a method.
So I have a tree like this:
A
/ \
B C
/ \ / \
D E F G
/ \
H I
/ \
J K
and my method is:
public BinaryTree preorderNext(BinaryTree t, BinaryTree v, BinaryTree prev) {
prev = t;
if(t.getLeft() != null) {
preorderNext(t.getLeft(), v, prev);
}
if(t.getRight() != null) {
preorderNext(t.getRight(), v, prev);
}
if(prev == v) {
return t;
}
return null;
}
The lecturer had given a simple implementation of the tree. The class is called BinaryTree and if you want to make a node link to it then you specify what the right and left child BinaryTree node are.
A node has two links (one to the left and the other to the right child) and there is no link to the head.
So with the current method I am able to successful do a preorder traversal, I tested by writing the print statements of what the element stored at the node is.
But when I run the tests, it tells me that the next preorder node from A is B, and the next preorder node from K throws a null exception but it should be I?
Any ideas of where I am going wrong? The variable prev should hold a reference to the last node visited so if it equals to node v (which is the node I specify, to return the node after v), shouldn't I get the next node?
Upvotes: 0
Views: 7315
Reputation: 343
I provide an answer that runs in O(h)
running time.
class Node {
public int key;
public Node l;
public Node r;
public Node p;
public Node(int key) {
this.key = key;
this.l = null;
this.r = null;
this.p = null;
}
}
public Node preorderNext(Node v) {
if (v.l != null) {
return v.l;
} else if (v.r != null) {
return v.r;
} else {
while (v.p != null) {
if (v == v.p.l) {
if (v.p.r != null) {
return v.p.r;
} else {
v = v.p;
}
} else {
if (v.p.p == null) {
return null;
} else if (v.p == v.p.p.l) {
if (v.p.p.r != null) {
return v.p.p.r;
} else {
v = v.p;
}
} else {
v = v.p;
}
}
}
return null;
}
}
Upvotes: 0
Reputation: 2575
I am not sure if doing that task recursively is that easy.
Solving the task the iterative way using a stack could be a much better approach:
public BinaryTree preOrderNext(BinaryTree toSearch) {
Stack<BinaryTree> openList = new Stack<BinaryTree>();
openList.push(root);
while (openList.empty() == false) {
BinaryTree curr = openList.pop();
if (curr.getRight() != null)
openList.push(curr.getRight());
if (curr.getLeft() != null)
openList.push(curr.getLeft());
if (curr.equals(toSearch) && openList.empty() == false){
return openList.pop();
}
}
return null;
}
This method is not tested, but should be working.
Upvotes: 1
Reputation: 1834
Here is an implementation of how a preorder traversal
is done recursively.
public void preOrderTraversal(BinaryTree root){
if(root == null) return;
System.out.println(root);
preOrderTraversal(root.getLeft());
preOrderTraversal(root.getRight());
}
Notes:
root
is null with that approach you can return an "emptyNode
" and deal with it by an if statement.root
, with any level the root
changes. Try to visualize this with a run-through and you will understand this concept.t
).You can continue to adapt your results to this.
A final note is for the run-time complexity of this approach, I'd highly recommend understanding run-time complexities for recursive functions. It will help you a lot in the future. Check this wikipedia article for recurrence relations.
Upvotes: 0