Recursive breadth-first travel function in Java or C++?
- by joejax
Here is a java code for breadth-first travel:
void breadthFirstNonRecursive(){
Queue<Node> queue = new java.util.LinkedList<Node>();
queue.offer(root);
while(!queue.isEmpty()){
Node node = queue.poll();
visit(node);
if (node.left != null)
queue.offer(node.left);
if (node.right != null)
queue.offer(node.right);
}
}
Is it possible to write a recursive function to do the same?
At first, I thought this would be easy, so I came out with this:
void breadthFirstRecursive(){
Queue<Node> q = new LinkedList<Node>();
breadthFirst(root, q);
}
void breadthFirst(Node node, Queue<Node> q){
if (node == null) return;
q.offer(node);
Node n = q.poll();
visit(n);
if (n.left != null)
breadthFirst(n.left, q);
if (n.right != null)
breadthFirst(n.right, q);
}
Then I found it doesn't work. It is actually does the same thing as this:
void preOrder(Node node) {
if (node == null) return;
visit(node);
preOrder(node.left);
preOrder(node.right);
}
Has any one thought about this before?
