There are 2 approaches to traversing a binary tree: use Depth-First search (DFS) and Breadth-First search (BFS). In case of DFS, we process the tree as follows:
In-Order processing:
- make a recursive call on the left child (1)
- analyze node value (2)
- make a recursive call on the right child (3)
Pre-Order processing:
- analyze a node value (1)
- make a recursive call on the left child (2)
- make a recursive call on the right child (3)
Post-Order processing:
- make a recursive call on the left child (1)
- make a recursive call on the right child (2)
- analyze a node value (3)
Time complexity: O(n)
Space complexity: O(m), where m – max depth of the tree
public class ImplementDFSInBinaryTree {
private static void dfsPreOrder(Node node) {
System.out.println(node.value);
if(node.left!=null) {
dfsPreOrder(node.left);
}
if(node.right!=null) {
dfsPreOrder(node.right);
}
}
private static void dfsInOrder(Node node) {
if(node.left!=null) {
dfsInOrder(node.left);
}
System.out.println(node.value);
if(node.right!=null) {
dfsInOrder(node.right);
}
}
private static void dfsPostOrder(Node node) {
if(node.left!=null) {
dfsPostOrder(node.left);
}
if(node.right!=null) {
dfsPostOrder(node.right);
}
System.out.println(node.value);
}
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("DFS preOrder:");
dfsPreOrder(tree.root);
System.out.println("DFS inOrder:");
dfsInOrder(tree.root);
System.out.println("DFS postOrder:");
dfsPostOrder(tree.root);
}
}
Pingback: DFS in Graphs – Mike Scherbakov