Depth first search traversals

Back to index

We carry out the three common types of depth first search without using recursion. To keep track of where we are in the tree we use a stack, which we call the search path. The difference between the pre-order, in-order and post-order traversals is simply the stage at which we add the node to the output list. Note that we use an additional set to keep track of the nodes we have visited. This way we don't have to modify the original tree. If it was for some reason preferable to modify the original tree (perhaps to save memory) then we could instead set the appropriate pointers to null.

Also note that we use an ArrayDeque to implement a Deque.

The pre-order traversal adds the node to the output list before processing the left or the right sub-tree.

public List<Integer> preorderTraversal(TreeNode root) {
  List<Integer> preOrder = new LinkedList<>();
  if (root == null) {
    return preOrder;
  }

  Deque<TreeNode> searchPath = new ArrayDeque<>();
  Set<TreeNode> visited = new HashSet<>();

  searchPath.push(root);

  while (searchPath.size() > 0) {
    TreeNode node = searchPath.peek();

    if (!visited.contains(node)) {
      preOrder.add(node.val);
      visited.add(node);
    }

    if (node.left != null && !visited.contains(node.left)) {
      searchPath.push(node.left);
      continue;
    }

    if (node.right != null && !visited.contains(node.right)) {
      searchPath.push(node.right);
      continue;
    }

    searchPath.pop();
  }

  return preOrder;
}

The in-order traversal adds the node to the output list in between processing the left and the right sub-tree.

public List<Integer> preorderTraversal(TreeNode root) {
  List<Integer> preOrder = new LinkedList<>();
  if (root == null) {
    return preOrder;
  }

  Deque<TreeNode> searchPath = new ArrayDeque<>();
  Set<TreeNode> visited = new HashSet<>();

  searchPath.push(root);

  while (searchPath.size() > 0) {
    TreeNode node = searchPath.peek();

    if (node.left != null && !visited.contains(node.left)) {
      searchPath.push(node.left);
      continue;
    }

    if (!visited.contains(node)) {
      preOrder.add(node.val);
      visited.add(node);
    }

    if (node.right != null && !visited.contains(node.right)) {
      searchPath.push(node.right);
      continue;
    }

    searchPath.pop();
  }

  return preOrder;
}

The post-order traversal adds the node to the output list after processing the left and the right sub-tree.

public List<Integer> preorderTraversal(TreeNode root) {
  List<Integer> preOrder = new LinkedList<>();
  if (root == null) {
    return preOrder;
  }

  Deque<TreeNode> searchPath = new ArrayDeque<>();
  Set<TreeNode> visited = new HashSet<>();

  searchPath.push(root);

  while (searchPath.size() > 0) {
    TreeNode node = searchPath.peek();

    if (node.left != null && !visited.contains(node.left)) {
      searchPath.push(node.left);
      continue;
    }

    if (node.right != null && !visited.contains(node.right)) {
      searchPath.push(node.right);
      continue;
    }

    if (!visited.contains(node)) {
      preOrder.add(node.val);
      visited.add(node);
    }

    searchPath.pop();
  }

  return preOrder;
}