Backtracking in Binary Trees: Solving Pathfinding Problems

What is Tree Backtracking?

Backtracking is a search or traversal method used to solve problems that can be framed as navigating through a tree structure. It is used in scenarios where you need to explore all the possible paths in a tree to find a solution.

Example 1: Solving the “Path Exists” Problem

The simplest example of backtracking is determining if there’s a path from the root to a leaf node in a binary tree without encountering any 0s. And if there’s a path, we will return true, otherwise, we return false.

Here is the pseudocode of the solution algorithm we will be using to solve the problem.

1. Start at the Root: Begin searching from the root node of the tree.
2. Check for Null Node: If the current node is null, return false (as it doesn’t lead to a leaf).
3. Check for Zero Value: If the current node’s value is 0, return false, as the path contains a 0.
4. Check for Leaf Node: If the current node is a leaf (no children), return true, as you’ve found a path without a 0.
5. Recursive Exploration: Recursively check the left and right subtrees. If either subtree returns true (meaning a valid path is found), propagate true upwards.
6. Backtrack if Needed: If no valid path is found in the current subtree, backtrack, i.e., return to the previous node and explore other paths.

function hasValidPath(node) {
    // Check if the current node is null
    if (node === null) {
        return false;
    }

    // Check if the current node's value is 0
    if (node.val === 0) {
        return false;
    }

    // Check if the current node is a leaf node (no children)
    if (node.left === null && node.right === null) {
        return true; // Found a valid path
    }

    // Recursively check the left and right subtrees
    return hasValidPath(node.left) || hasValidPath(node.right);
}

The backtracking algorithm has a time complexity of O(N) since every possible scenario must be explored in the worst-case scenario.

Example 2: Solving the “Return-Path” Problem

Now, let's consider the same example, but in this case, we have to return the full path to that node instead of returning true or false.

In this case, we need to modify the backtracking algorithm to keep track of the path as it explores the tree. When a valid path is found, we return the path itself instead of just a true value. If the path is not valid or a dead end is reached, we backtrack, removing the last added node from the path.

function findPath(root) {
    function backtrack(node, path) {
        // Check if the current node is null or its value is 0
        if (!node || node.val === 0) {
            return null;
        }

        // Add the current node's value to the path
        path.push(node.val);

        // Check if the current node is a leaf node (no children)
        if (!node.left && !node.right) {
            // Return the copy of the current path as it's a valid path
            return path.slice();
        }

        // Recursively check the left and right subtrees
        let leftPath = backtrack(node.left, path);
        if (leftPath) {
            return leftPath;
        }

        let rightPath = backtrack(node.right, path);
        if (rightPath) {
            return rightPath;
        }

        // Backtrack: remove the current node's value from the path
        path.pop();
        return null;
    }

    return backtrack(root, []);
}

Here’s how the solution algorithm works: We have a backtrack helper method that takes care of the path-finding logic:

1. Start at the root with an empty list to record the path.
2. If a node is null or its value is 0, the path is invalid; return null.
3. Add the node’s value to the path list if it’s valid (non-zero and not null).
4. If the node is a leaf (no left or right child), return the current path as a valid result.
5. Recursively search left, then right:
   If a valid path is found in the left subtree, return it.
   If not, search in the right subtree. If found, return it.
6. If no valid path is found (neither left nor right yields a result), backtrack by removing the last node from the path list and return null.
7. Return the first valid path found from the root to a leaf where no node’s value is 0 or null if there isn’t one.

The time complexity of this algorithm is also O(N). In general, the worst case for all backtracking algorithms is O(b^n), where ‘b’ is the branching factor (the average number of children at each node), and ’n’ is the depth of the decision tree. This is because, in the worst case, you might need to explore each possible path in the solution space.

Backtracking Algorithm Use Cases

Some other classic problems and use cases of backtracking algorithms are:

1. Puzzle Games:

• Sudoku: Filling in a 9x9 grid with digits so that each column, each row, and each of the nine 3x3 subgrids contain all of the digits from 1 to 9.
• N-Queens Problem: Placing N chess queens on an N×N chessboard so that no two queens threaten each other. The solution requires that no two queens share the same row, column, or diagonal.

2. Combinatorial Problems:

• Permutations: Generating all possible arrangements of a set of items where the order of arrangement is important.
• Combinations: Finding all possible selections of a set of items where the order is not important.

3. Subset Problems:

• Subset Sum: Finding a subset of a given set of integers whose sum equals a given number. This is particularly used in financial analysis or strategic planning, where specific combinations of investments are evaluated.
• Knapsack Problem: Selecting a subset of items with given weights and values to maximize the value in a knapsack of limited capacity.

4. Path Finding and Graph Problems:

• Hamiltonian Cycles: Finding a path in a graph that visits each vertex exactly once and returns to the starting vertex.
• Maze Solving: Finding a path from the entrance to the exit of a maze, navigating through open paths, and avoiding blocked ones.

Thanks for the read! For weekly insights on web development that you won’t want to miss, subscribe to My Newsletter.

Hayk Simonyan | Substack