Problem

Given the root of a binary tree, return all root-to-leaf paths in any order.

A leaf is a node with no children.

Examples

Example 1:

     1
    / \
   2   3
   \
    5

Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]

Solution

Method 1 - DFS

Here is the approach:

  1. We use Depth-First Search (DFS) to explore all paths from the root to the leaves.
  2. Keep track of the current path as we go deeper into the tree.
  3. When we reach a leaf node, add the current path to the result.
  4. Backtrack and continue the search until all paths are found.

Code

Java
public class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> ans = new ArrayList<>();
        if (root == null) return ans;
        dfs(root, "", ans);
        return ans;
    }

    private void dfs(TreeNode node, String path, List<String> ans) {
        if (node == null) return;

        path += node.val;

        if (node.left == null && node.right == null) { // leaf node
            ans.add(path);
        } else {
            path += "->";
            dfs(node.left, path, ans);
            dfs(node.right, path, ans);
        }
    }
}
Python
class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        ans: List[str] = []
        if not root:
            return ans
        self._dfs(root, "", ans)
        return ans

    def _dfs(self, node: TreeNode, path: str, ans: List[str]) -> None:
        if not node:
            return
        
        path += str(node.val)
        
        if not node.left and not node.right:  # leaf node
            ans.append(path)
        else:
            path += "->"
            self._dfs(node.left, path, ans)
            self._dfs(node.right, path, ans)

Complexity

  • ⏰ Time complexity: O(n), where n is the number of nodes in the tree as we visit each node exactly once.
  • 🧺 Space complexity: O(h) = O(n) as in the worst case, the space complexity is proportional to the height of the tree due to the recursion stack.