Solution: Binary Tree Paths

Statement

Given the root of a binary tree, return all paths from the root to the leaf nodes in any order. Each path should be represented as a string of node values, separated by arrows (→), where a leaf is defined as a node with no children.

Constraints:

• $1\leq$ nodes $\leq 100$

• $-10^4\leq$ nodes.data $\leq10^4$

Solution

This solution traverses a binary tree from the root to each leaf node while keeping track of the path taken. The intuition behind this approach is that by using backtracking, we can explore all possible paths in the tree, ensuring that we capture each unique route from the root to the leaves. When a leaf node is reached, the complete path from the root to that leaf is stored. The solution then backtracks to the previous node to explore other paths, repeating this process until all root-to-leaf paths are recorded.

Here’s the step-by-step implementation of the solution:

• Initialize an empty list, paths, to collect all the root-to-leaf paths. After the recursive traversal of the tree is complete, this list will contain all the paths.

• A helper function backtrack takes two arguments: the current root node and the path. This function’s role is to recursively explore each tree branch while building the path.

• Base case: First, check whether the current node is NULL. If it is not, do the following:

  • Convert the current node’s data to a string and append it to the path. This keeps track of the path from the root to the current node.

  • If the current node is a leaf:

    • The path string (the path from the root to this leaf) is appended to the paths list.

  • If the node is not a leaf:

    • Add '→' to the path to add a connection to the next node.

    • Recursively call backtrack on the left and right children of the current node to explore both paths.

• Finally, return the paths list, which holds all the root-to-leaf paths in the tree.

Let’s look at the following illustration to get a better understanding of the solution: