There are 2 approaches to traversing a binary tree: use Depth-First search (DFS) and Breadth-First search (BFS). In case of BFS, we process the tree as follows:
Iterative processing:
- start from the root node
- push current node into queue
- while the queue is not empty:
– poll the queue to retrieve node to process
– analize the value of the retireved node
– put to the queue both childs of the retireved node.
Recursive processing:
- start from the root node
- push current node into queue
- if the queue is not empty:
– poll the queue to retrieve node to process
– analize the value of the retireved node
– put to the queue both childs of the retireved node. - make a recursive call to itself
Time complexity: O(n)
Space complexity: O(l), where l – max width of the tree
import java.util.LinkedList;
public class ImplementBFSInBinaryTree {
private static void bfsIterative(Node node) {
var queue = new LinkedList<Node>();
queue.push(node);
while (!queue.isEmpty()) {
var curNode = queue.poll();
System.out.println(curNode.value);
if (curNode.left != null) {
queue.add(curNode.left);
}
if (curNode.right != null) {
queue.add(curNode.right);
}
}
}
private static void bfsRecursive(LinkedList<Node> queue) {
if (queue.isEmpty()) {
return;
}
var curNode = queue.poll();
System.out.println(curNode.value);
if (curNode.left != null) {
queue.add(curNode.left);
}
if (curNode.right != null) {
queue.add(curNode.right);
}
bfsRecursive(queue);
}
public static void main(String[] args) {
var tree = new BinaryTree<>(50);
tree.insert(10);
tree.insert(5);
tree.insert(15);
tree.insert(60);
tree.insert(55);
tree.insert(65);
System.out.println("BFS iterative:");
bfsIterative(tree.root);
System.out.println("BFS recursive:");
var queue = new LinkedList<Node>();
queue.push(tree.root);
bfsRecursive(queue);
}
}