257. Binary Tree Paths

EasyTreeDepth-First SearchStringBacktrackingBinary Tree

Problem Description

The problem presents us with a binary tree, where each node contains an integer value and can have a left and/or right child. Our goal is to find all the unique paths from the root of the binary tree to its leaves. A leaf is defined as a node that has no children, which means neither a left nor a right child. The paths should be represented as strings, with each node's value on the path concatenated by "->". For instance, if the path goes through nodes with values 1, 2, and 3 in that order, the path string should be "1->2->3". We are required to return these path strings in any order.

Flowchart Walkthrough

Let's utilize the algorithm Flowchart to determine the appropriate technique for solving Leetcode 257, Binary Tree Paths. Here's the step-by-step analysis:

Is it a graph?

Yes: In this problem, the binary tree can be treated as a graph.

Is it a tree?

Yes: It specifically uses a binary tree data structure.

Is the problem related to directed acyclic graphs (DAGs)?

Not applicable since "Is it a tree?" directed us straight to "DFS".

Conclusion: The flowchart directs us to use Depth-First Search (DFS), which is suitable for exploring all paths in a tree structure, especially useful in problems like generating all paths from root to leaf in a binary tree.

Intuition

To solve this problem, we can utilize a technique called Depth-First Search (DFS). This strategy explores as far as possible along each branch before backtracking. Here's how we arrive at the solution approach:

We can start at the root and perform a DFS traversal on the binary tree.
As we traverse, we keep track of the current path by noting the nodes visited so far in the sequence.
Whenever we reach a leaf node (a node without children), we record the path we've taken to get there. This is a complete root-to-leaf path, so we add this to our list of answers.
The key part of this process is backtracking. When we visit a node and explore all of its children, we backtrack, which means we remove the node from our current path and return to the previous node to explore other paths.
We continue this process until all paths are explored and we have visited all the leaves.

The recursive function dfs() in the solution code is where the DFS takes place. It takes the current node as a parameter, and as the function is called recursively, a local variable t keeps track of the current path as a list of node values. If a leaf node is reached, the current path is converted to the path string format required and added to the list ans, which contains all the full path strings. After exploring a node's left and right children, the node's value is popped from the path list to allow backtracking to the previous node's state.

Learn more about Tree, Depth-First Search, Backtracking and Binary Tree patterns.

Solution Approach

The solution approach for the given problem utilizes a typical pattern for tree traversal problems, which is the Depth-First Search (DFS) algorithm. Here's a step-by-step explanation of how the solution is implemented:

Define a Recursive Function (dfs): The recursive function dfs is defined within the class Solution. It is invoked with the current node being visited. This function does not return any value but instead updates the ans list with the path strings.
Base Case for Recursion: In the function dfs, before going further into recursion, we check if the given root node is None, indicating that we've reached beyond a leaf node. In this case, the function simply returns without performing any further action.
Track the Current Path: A local variable t in the class scope is used to keep track of the current path. It's a stack (implemented using a list in Python) that we update as we go down the tree. For each node, we convert its value to a string and append it to t.
Check for Leaf Node: In the DFS process, if the current node is a leaf (both left and right child nodes are None), we convert the current path into the required string format, which is obtained by joining the sequence of node values in t with "->". This complete path string is added to the ans list.
Recursive DFS Calls: If the current node has children, we perform DFS for both the left child (if not None) and right child (if not None). The function calls itself with root.left and root.right correspondingly.
Backtracking: After exploring both children from the current node, we need to backtrack. This ensures that when we return from the recursive call, the current path t reflects the state as if the current node was never visited. We achieve this by popping the last value from the t.
Return Paths: Once the DFS is complete, the ans list will be populated with all the path strings from root to all the leaf nodes. This list is returned as the final result of the binaryTreePaths method.

The use of a stack for tracking the paths and the pattern of adding to the list only at leaf nodes are critical parts of the algorithm. The recursive DFS makes sure all potential paths are explored, while backtracking ensures that every unique path is properly captured without duplication.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach using a small example binary tree:

Consider the following binary tree:

Here's how we would apply the solution approach:

We start with the root node which is 1.
We initialize t with the value of the current node: t = ["1"].
The node 1 is not a leaf, so we continue. We have two recursive DFS calls to make because both left and right children exist: root.left (which is 2) and root.right (which is 3).
First DFS call: We move to the left child which is 2 and update t to ["1", "2"].
Node 2 has a left child but no right child. We make a recursive DFS call to the left child which is 5.
On reaching the node 5, we update t to ["1", "2", "5"].
Node 5 is a leaf node, so we join the elements of t with "->" to form the path string "1->2->5". We add this to our ans list.
Backtracking: We finished visiting 5, so we pop it from t making t = ["1", "2"].
There are no more children for 2 to visit, so we pop it from t as well. Now t = ["1"].
Second DFS call: Now, we explore the right child of 1, which is 3. We update t to ["1", "3"].
Node 3 has a right child 4 but no left child. We make a recursive DFS call to the right child which is 4.
On reaching 4, we update t to ["1", "3", "4"].
Node 4 is a leaf node, so we join the elements of t with "->" to form the path string "1->3->4". We add this to our ans list.
Backtracking: We've visited 4, so we pop it from t, reverting t back to ["1", "3"].
After exploring node 3's right child, we backtrack one more time, popping 3 from t and t is now back to ["1"].

Finally, since all paths have been explored, our ans list contains the root-to-leaf path strings: ["1->2->5", "1->3->4"]. We'd return this list as the output of our function.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
10      
11        # Perform Depth-First Search (DFS) to find all paths
12        def dfs(node: Optional[TreeNode]):
13            # If the current node is None, return without doing anything
14            if node is None:
15                return
16          
17            # Append the current node's value to the path
18            path.append(str(node.val))
19          
20            # If the current node is a leaf node, add the path to the results
21            if node.left is None and node.right is None:
22                all_paths.append("->".join(path))
23            else:
24                # Otherwise, continue the DFS traversal
25                dfs(node.left)
26                dfs(node.right)
27          
28            # After traversing, remove the last node value from the path
29            path.pop()
30
31        # Initialize a list to store all paths as strings
32        all_paths = []
33      
34        # Initialize a temporary list to store the current path
35        path = []
36      
37        # Start the DFS with the root node
38        dfs(root)
39      
40        # Return all the root-to-leaf paths found
41        return all_paths
42

1/**
2 * Definition for a binary tree node.
3 */
4public class TreeNode {
5    int val;
6    TreeNode left;
7    TreeNode right;
8    TreeNode() {}
9    TreeNode(int val) { this.val = val; }
10    TreeNode(int val, TreeNode left, TreeNode right) {
11        this.val = val;
12        this.left = left;
13        this.right = right;
14    }
15}
16
17class Solution {
18    // A list to store all path strings
19    private List<String> allPaths = new ArrayList<>();
20    // A temporary list to keep the current path nodes
21    private List<String> currentPath = new ArrayList<>();
22
23    /**
24     * Finds all paths from root to leaf in a binary tree.
25     *
26     * @param root The root of the binary tree.
27     * @return A list of all root-to-leaf paths in string format.
28     */
29    public List<String> binaryTreePaths(TreeNode root) {
30        // Perform a depth-first search starting from the root
31        depthFirstSearch(root);
32        return allPaths;
33    }
34
35    /**
36     * Performs a recursive depth-first search to find all paths.
37     *
38     * @param node The current node in the binary tree.
39     */
40    private void depthFirstSearch(TreeNode node) {
41        if (node == null) {
42            // Base case: if node is null, do nothing
43            return;
44        }
45      
46        // Append current node's value to the path
47        currentPath.add(String.valueOf(node.val));
48      
49        // If node is a leaf, add the path to the list of all paths
50        if (node.left == null && node.right == null) {
51            allPaths.add(String.join("->", currentPath));
52        } else {
53            // Recur for left and right children
54            depthFirstSearch(node.left);
55            depthFirstSearch(node.right);
56        }
57
58        // Backtrack: remove the last node from the path before returning
59        currentPath.remove(currentPath.size() - 1);
60    }
61}
62

1// Definition of the binary tree node.
2struct TreeNode {
3    int val; // Node value.
4    TreeNode *left; // Pointer to left child.
5    TreeNode *right; // Pointer to right child.
6  
7    // Constructor for creating a leaf node.
8    TreeNode() : val(0), left(nullptr), right(nullptr) {}
9  
10    // Constructor for creating a node with a specific value.
11    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
12  
13    // Constructor for creating a node with specific value, left child, and right child.
14    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
15};
16
17class Solution {
18public:
19    // Finds all root-to-leaf paths in the binary tree.
20    vector<string> binaryTreePaths(TreeNode* root) {
21        vector<string> paths;              // Stores all the paths from root to leaf.
22        vector<string> currentPathNodes;   // Tracks nodes of the current path.
23      
24        // Depth-first search to traverse the tree and build paths.
25        function<void(TreeNode*)> dfs = [&](TreeNode* node) {
26            if (!node) {
27                return; // Base case: if the current node is null, just return.
28            }
29          
30            // Add the current node value to the path.
31            currentPathNodes.push_back(to_string(node->val));
32          
33            // If the current node is a leaf, join the current path and add to paths.
34            if (!node->left && !node->right) {
35                paths.push_back(join(currentPathNodes));
36            } else {
37                // Recursively call DFS on the non-null children.
38                dfs(node->left);
39                dfs(node->right);
40            }
41            // Backtracking step: remove the current node value from the path.
42            currentPathNodes.pop_back();
43        };
44      
45        // Start DFS from the root node.
46        dfs(root);
47        return paths;
48    }
49
50    // Helper function to create a string from vector of strings representing nodes.
51    string join(const vector<string>& tokens, const string& separator = "->") {
52        string path;
53        for (size_t i = 0; i < tokens.size(); ++i) {
54            if (i > 0) {
55                path += separator;
56            }
57            path += tokens[i];
58        }
59        return path; // Return the joined path as a string.
60    }
61};
62

1// Represents a tree node with a numerical value and optional left and right children.
2type TreeNode = {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6};
7
8/**
9 * Helper function that performs a Depth-First Search on the binary tree to find all paths from the
10 * root to leaf nodes.
11 *
12 * @param node The current node being visited in the DFS traversal.
13 * @param path The list of values collected so far from the root to the current node.
14 * @param paths The list of all paths from the root to leaf nodes represented as strings.
15 */
16function traverseAndRecordPaths(node: TreeNode | null, path: number[], paths: string[]): void {
17    // Base case: if the current node is null, return to avoid further processing.
18    if (!node) {
19        return;
20    }
21
22    // Append the current node's value to the path.
23    path.push(node.val);
24
25    // Check if the current node is a leaf node (no left and right children).
26    if (!node.left && !node.right) {
27        // If it's a leaf, add the path to the list of paths as a string.
28        paths.push(path.join('->'));
29    } else {
30        // If not a leaf, recursively search the left and right subtrees.
31        traverseAndRecordPaths(node.left, path, paths);
32        traverseAndRecordPaths(node.right, path, paths);
33    }
34
35    // Pop the last node's value from the path after exploring all paths from here.
36    path.pop();
37}
38
39/**
40 * Encapsulates the process of collecting all paths in a binary tree from root to leaf nodes.
41 *
42 * @param root The root of the binary tree.
43 * @return The list of all root-to-leaf paths as strings.
44 */
45function binaryTreePaths(root: TreeNode | null): string[] {
46    // Initialize an array to store all root-to-leaf paths.
47    const allPaths: string[] = [];
48    // Temporary variable to store the current path in the recursion.
49    const currentPath: number[] = [];
50
51    // Perform the DFS traversal starting from the root to find all paths.
52    traverseAndRecordPaths(root, currentPath, allPaths);
53
54    // Return the collected paths.
55    return allPaths;
56}
57

Time and Space Complexity

The given Python function binaryTreePaths traverses a binary tree to find all root-to-leaf paths. The primary operation is a Depth-First Search (DFS) defined in a nested function. Here's the analysis of its complexities:

Time Complexity

The time complexity is O(N), where N is the number of nodes in the tree. This is because each node in the binary tree is visited exactly once during the depth-first search. Therefore, the function's time complexity is directly proportional to the number of nodes.

Space Complexity

The space complexity of the function is also O(N). The major factors contributing to the space complexity are:

The recursive call stack of the DFS, which in the worst case could be O(N) when the binary tree degrades to a linked list.
The list t that holds the current path. In the worst case, when the binary tree is completely skewed (e.g., each parent has only one child), this list can also take up to O(N) space.
The list ans that contains all the paths. In the best case, where each node has two children, there will be N/2 leaf nodes resulting in N/2 paths. Although each path could be of varying length, the concatenation of all paths will still take O(N) space since each node's value is only included in one path string.

Considering the stack space for recursive calls and the space for storing the paths, the space complexity in the worst case scenario will be linear with respect to the number of nodes in the tree.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Is the following code DFS or BFS?

void search(Node root) {
  if (!root) return;
  visit(root);
  root.visited = true;
  for (Node node in root.adjacent) {
    if (!node.visited) {
      search(node);
    }
  }
}

Depth First Search

Breadth First Search

I don't know