Domain 1EasyCORE

Binary Tree Paths

The problem requires us to find all root-to-leaf paths in a binary tree. A leaf node is defined as a node with no children. The input is the root of the binary tree, and the output should be a list of strings representing each path from the root to a leaf.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Tree#Depth-first Search

257. Binary Tree Paths

Model: qwen2.5-coder:14b
Topics: Tree,Depth-first Search
FAANG asked: 1
Acceptance rate: 54.0%


Problem Breakdown

The problem requires us to find all root-to-leaf paths in a binary tree. A leaf node is defined as a node with no children. The input is the root of the binary tree, and the output should be a list of strings representing each path from the root to a leaf.

Inputs:

  • root: The root node of the binary tree.

Outputs:

  • A list of strings where each string represents a path from the root to a leaf node. Each path is formatted as “node1->node2->…->nodeN”.

Implicit Constraints or Tricky Edge Cases:

  • The tree can be empty (though the problem guarantees at least one node).
  • Nodes can have negative values.
  • The tree could be unbalanced.

Intuition

A brute-force approach would involve traversing all possible paths from the root to the leaf nodes and collecting them. This would be inefficient because it doesn’t take advantage of any properties of binary trees or optimize the traversal process.

The key insight is to use Depth-first Search (DFS) to explore each path from the root to the leaves. DFS is suitable here because it allows us to traverse down one branch as far as possible before backtracking, which aligns well with exploring paths in a tree structure.

Approach

  1. Initialize an empty list paths to store all the root-to-leaf paths.
  2. Define a helper function dfs(node, path) that takes the current node and the current path as arguments.
  3. If the current node is None, return immediately (base case for recursion).
  4. Append the current node’s value to the path.
  5. If the current node is a leaf (both left and right children are None), convert the path list to a string with ”->” as separators and add it to the paths list.
  6. Recursively call dfs on the left child of the current node, passing the updated path.
  7. Recursively call dfs on the right child of the current node, passing the updated path.
  8. After exploring both children, backtrack by removing the last element from the path (backtracking step).
  9. Call the dfs function starting with the root node and an empty path list.
  10. Return the paths list containing all root-to-leaf paths.

Complexity Analysis

  • Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited once during the DFS traversal.
  • Space Complexity: O(H + N), where H is the height of the tree and N is the number of leaf nodes. The space complexity includes the recursion stack (up to H calls) and the storage for paths (N paths).

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def binaryTreePaths(root: TreeNode) -> list[str]:
    paths = []
    
    def dfs(node, path):
        if not node:
            return
        path.append(str(node.val))
        if not node.left and not node.right:
            paths.append("->".join(path))
        dfs(node.left, path)
        dfs(node.right, path)
        path.pop()
    
    dfs(root, [])
    return paths

Edge Cases Handled

  • Single Node Tree: If the tree consists of only one node (the root), the function will correctly return a single-element list containing just that node’s value.
  • Empty Tree: Although the problem guarantees at least one node, if we were to handle an empty tree, the function would return an empty list.
  • Negative Node Values: The function handles negative values by converting them to strings and appending them to the path.