Solution: Binary Tree Paths
Let’s solve the Binary Tree Paths problem using the Backtracking pattern.
We'll cover the following
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:
nodes
nodes.data
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 currentroot
node and thepath
. 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 thepaths
list.
If the node is not a leaf:
Add
'→'
to thepath
to add a connection to the next node.Recursively call
backtrack
on theleft
andright
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:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.