Binary Tree Paths

Difficulty: Easy | Acceptance: 68.60% | Paid: No Topics: String, Backtracking, Tree, Depth-First Search, Binary Tree

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
• Constraints
• Approach 1: Depth-First Search (DFS) - Recursive
• Approach 2: Breadth-First Search (BFS)
• Approach 3: Depth-First Search (DFS) - Iterative

Examples

Example 1:

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

Example 2:

Input: root = [1]
Output: ["1"]

Constraints

The number of nodes in the tree is in the range [1, 100].
-100 <= Node.val <= 100

Approach 1: Depth-First Search (DFS) - Recursive

Intuition We traverse the tree using a pre-order depth-first search strategy. As we visit each node, we append its value to a string representing the current path. When we reach a leaf node (a node with no left or right children), we add the constructed path string to our result list.

Steps

• Define a helper function that takes a node and the current path string as arguments.
• If the node is null, return immediately.
• Append the current node’s value to the path string.
• Check if the node is a leaf (both left and right children are null). If so, add the path to the result list.
• If the node is not a leaf, append ”->” to the path string and recursively call the helper function for the left and right children.

class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        paths = []
        
        def construct_paths(node, path):
            if node:
                path += str(node.val)
                if not node.left and not node.right:
                    paths.append(path)
                else:
                    path += "->"
                    construct_paths(node.left, path)
                    construct_paths(node.right, path)
                    
        construct_paths(root, "")
        return paths

Complexity

• Time: O(N), where N is the number of nodes. We visit each node exactly once.
• Space: O(N), in the worst case (skewed tree), the recursion stack can grow as deep as the number of nodes. Additionally, storing the output takes O(N * L) where L is the average path length, but typically we consider auxiliary space O(N).
• Notes: This is the most intuitive approach for tree traversal problems.

Approach 2: Breadth-First Search (BFS)

Intuition We can solve this problem iteratively using a queue. Instead of recursion, we traverse the tree level by level. We store pairs of (node, path_string) in the queue. When we dequeue a node, we check if it is a leaf. If it is, we add the path to the results. If not, we enqueue its children with the updated path string.

Steps

• Initialize a queue containing the root node and its value converted to a string.
• While the queue is not empty, dequeue an element (node, path).
• If the node is a leaf (no children), add the path to the result list.
• If the node has a left child, enqueue (left_child, path + ”->” + left_child.val).
• If the node has a right child, enqueue (right_child, path + ”->” + right_child.val).

from collections import deque

class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        if not root:
            return []
        
        paths = []
        queue = deque([(root, str(root.val))])
        
        while queue:
            node, path = queue.popleft()
            
            if not node.left and not node.right:
                paths.append(path)
            if node.left:
                queue.append((node.left, path + "->" + str(node.left.val)))
            if node.right:
                queue.append((node.right, path + "->" + str(node.right.val)))
                
        return paths

Complexity

• Time: O(N), we visit each node once.
• Space: O(N), the queue can hold up to N nodes in the worst case (e.g., the last level of a complete binary tree).
• Notes: Useful for avoiding recursion stack overflow, though generally slightly more memory overhead than DFS for deep trees.

Approach 3: Depth-First Search (DFS) - Iterative

Intuition Similar to the recursive DFS, but we simulate the call stack explicitly using a stack data structure. This avoids recursion depth limits. We push nodes onto the stack along with the path string representing the route taken to reach them.

Steps

• Initialize a stack with the root node and its string value.
• While the stack is not empty, pop a (node, path) pair.
• If the node is a leaf, add the path to the result list.
• If the node has a right child, push (right_child, path + ”->” + right_child.val) onto the stack.
• If the node has a left child, push (left_child, path + ”->” + left_child.val) onto the stack. (Note: We push right then left so that left is processed first, mimicking standard pre-order traversal).

class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        if not root:
            return []
        
        paths = []
        stack = [(root, str(root.val))]
        
        while stack:
            node, path = stack.pop()
            
            if not node.left and not node.right:
                paths.append(path)
            if node.right:
                stack.append((node.right, path + "->" + str(node.right.val)))
            if node.left:
                stack.append((node.left, path + "->" + str(node.left.val)))
                
        return paths

Complexity

• Time: O(N), each node is processed once.
• Space: O(N), the stack can hold up to N nodes in the worst case.
• Notes: Iterative DFS is preferred in languages with strict recursion limits or for very deep trees.