Backtracking with Depth First Search Iteratively

Question

I was working on a coding problem which required me to find the path to a node. Using recursion and DFS, this was quite easy.

public ArrayList<Integer> ancestorsList = new ArrayList<Integer>();
public boolean printAncestors(TreeNode root, int nodeData) {

    if (root == null) return false;
    if (root.data == nodeData) return true;

    boolean found = printAncestors(root.left, nodeData) || printAncestors(root.right, nodeData);
    if (found) ancestorsList.add(root.data);

    return found;
}

However, I always had trouble converting a recursive algorithm to a iterative one even though recursion is just using the program stack. I played around with the code a bit, but it seems like the iterative algorithm would require a map that links the child node to it's parent in order to backtrack if the node is found.

I was just wondering if there was a simpler way, or if the simplest way really was using a map that linked the parent and child nodes so you could backtrack.

Thanks!

Answer 1

In order to make code simple,i assume the node is different each other by value.

Basic data structure:

@Getter
@Setter
@AllArgsConstructor
@NoArgsConstructor
@ToString
public class TreeNode implements Comparator<TreeNode> {
    private int value;
    private TreeNode left;
    private TreeNode right;

    @Override
    public int compare(TreeNode o1, TreeNode o2) {
        return o1.getValue() - o2.getValue();
    }
}

The code to find path：

private static List<TreeNode> findPath(TreeNode root, int val) {
        if (null == root) {
            return Collections.emptyList();
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        List<TreeNode> path = new ArrayList<>();

        while (!stack.isEmpty()) {
            TreeNode top = stack.pop();
            path.add(top);
            // check the value
            if (top.getValue() == val) {
                break;
            }

            if (top.getRight() != null) {
                stack.push(top.getRight());
            }
            if (top.getLeft() != null) {
                stack.push(top.getLeft());
            }

            // if the node is leaf,we need rollback the path
            if (null == top.getLeft() && null == top.getRight()) {
                if (stack.isEmpty()) {
                  path.clear();
                  break;
                }
                TreeNode nextTop = stack.peek();
                for (int i = path.size() - 1; i >= 0; i--) {
                    if (path.get(i).getRight() == nextTop || path.get(i).getLeft() == nextTop) {
                        path = path.subList(0, i + 1);
                        break;
                    }
                }
            }
        }

        return path;
    }

Test Case:

@Test
public void test_findPath() {
    TreeNode treeNode8 = new TreeNode(8, null, null);
    TreeNode treeNode9 = new TreeNode(9, null, null);
    TreeNode treeNode10 = new TreeNode(10, null, null);
    TreeNode treeNode4 = new TreeNode(4, treeNode8, null);
    TreeNode treeNode5 = new TreeNode(5, treeNode9, treeNode10);
    TreeNode treeNode2 = new TreeNode(2, treeNode4, treeNode5);
    TreeNode treeNode1 = new TreeNode(1, treeNode2, null);
    List<TreeNode> path = TreeNodeService.findPath(treeNode1, 10);
    Assert.assertEquals(path.size(),4);
    Assert.assertEquals(path.get(0).getValue(),1);
    Assert.assertEquals(path.get(1).getValue(),2);
    Assert.assertEquals(path.get(2).getValue(),5);
    Assert.assertEquals(path.get(3).getValue(),10);
}

Note: If you tree has two or more nodes has the same value,you need to change some codes.You can try youself.