Loading problems...
TL;DR: The optimal solution utilizes a Depth-First Search (DFS) strategy, specifically recursive preorder traversal, to construct path strings incrementally as the algorithm navigates from the root down to each leaf node.
The "Binary Tree Paths" problem requires us to generate a list of all distinct paths from the root of a binary tree to its leaves. A path is defined as a sequence of nodes starting at the root and ending at a node with no children, connected by arrows (e.g., "1->2->5"). This is a fundamental tree traversal challenge that tests your ability to maintain state (the current path) while navigating the tree structure.
This LeetCode 257 solution focuses on constructing these strings efficiently during traversal.
A common naive approach to solving Binary Tree Paths is to perform a Breadth-First Search (BFS) where every node in the queue stores not just the node reference, but the entire path string constructed so far.
While technically correct, this approach can be memory-intensive. In a dense tree, the queue becomes very large. Furthermore, string concatenation and copying at every level in a BFS manner can lead to high constant factors in memory usage compared to a DFS approach that utilizes the call stack.
While BFS finds the shortest path in unweighted graphs, "Binary Tree Paths" requires all paths. BFS does not offer an algorithmic advantage here and often requires more complex code to manage the queue of pairs (Node, String). The recursive structure of trees naturally lends itself to a DFS solution, which is generally cleaner to implement and easier to reason about for full-tree traversals.
The key intuition for the LeetCode 257 solution is that a path from the root to any node N is simply the path from the root to N's parent, extended by N.
By using Recursive Preorder Traversal, we can pass the "history" of the path down the recursion stack. When the recursive function is called for a specific node, it receives the partial path constructed so far.
current_path string as an argument.Imagine the recursion tree. Execution starts at the root. The algorithm appends "1". It then pauses the root's context and moves left to "2", passing "1->2". It reaches a leaf, saves "1->2", and returns. The recursion unwinds back to "1", which then calls the right child "3", passing "1->3". The branching of the tree structure mirrors the branching of the string construction.

We will implement a dfs helper function that takes the current node and the current_path string.
null, return immediately. This handles edge cases and simplifies leaf logic.current_path. If the current_path was not empty, precede the value with "->".node.left == null and node.right == null).
current_path to our global result list.dfs on node.left with the updated current_path.dfs on node.right with the updated current_path.This strategy ensures we visit every node exactly once and construct paths in a top-down manner.
Let's trace the algorithm with Input: root = [1, 2, 3, null, 5]
Call DFS(1, ""):
Inside DFS(2, "1"):
Inside DFS(5, "1->2"):
Back in DFS(2, "1"):
Back in DFS(1, ""):
Inside DFS(3, "1"):
Final Result: ["1->2->5", "1->3"].
The correctness relies on the structural induction of the binary tree:
L (left) and R (right). When at the parent P, the algorithm constructs the prefix "Path(Root...P)". It then passes this prefix to L. By assumption, L will complete all paths starting with "Path(Root...P)->L...". The same applies to R.cppclass Solution { public: void dfs(TreeNode* node, string path, vector<string>& result) { if (!node) return; // Append current node value path += to_string(node->val); // Check if it is a leaf node if (!node->left && !node->right) { result.push_back(path); } else { // If not a leaf, continue traversal with arrow path += "->"; dfs(node->left, path, result); dfs(node->right, path, result); } } vector<string> binaryTreePaths(TreeNode* root) { vector<string> result; dfs(root, "", result); return result; } };
javaclass Solution { public List<String> binaryTreePaths(TreeNode root) { List<String> result = new ArrayList<>(); if (root != null) { dfs(root, "", result); } return result; } private void dfs(TreeNode node, String path, List<String> result) { // Append current node to path path += Integer.toString(node.val); // Check if leaf if (node.left == null && node.right == null) { result.add(path); } else { // Recurse with arrow appended path += "->"; if (node.left != null) dfs(node.left, path, result); if (node.right != null) dfs(node.right, path, result); } } }
pythonclass Solution: def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]: result = [] def dfs(node, path): if not node: return # Construct current path path += str(node.val) # If leaf, add to result if not node.left and not node.right: result.append(path) else: # Recurse dfs(node.left, path + "->") dfs(node.right, path + "->") dfs(root, "") return result
Let be the number of nodes in the tree.
Time Complexity: or depending on tree structure.
Space Complexity: or .
The Tree DFS - Recursive Preorder Traversal pattern is highly versatile. Understanding the logic in LeetCode 257 helps with:
Here are frequent errors candidates make when implementing this pattern:
Q: Why is my output containing paths that end in the middle of the tree?
node == null as the condition to add.Q: Why do I have extra arrows "->" at the end of my strings?
Q: Why am I getting a NullPointerException?
node.left or node.right without first checking if itself is null in the recursive call.nodeif (!node) return; at the start of your DFS helper.Q: Why does the solution fail on large inputs (Time Limit Exceeded)?