DFS in Tree (Pre-order, In-order, Post-order)

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);
  }
}

Related Posts