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
- Initialize an empty list
pathsto store all the root-to-leaf paths. - Define a helper function
dfs(node, path)that takes the current node and the current path as arguments. - If the current node is
None, return immediately (base case for recursion). - Append the current node’s value to the
path. - If the current node is a leaf (both left and right children are
None), convert thepathlist to a string with ”->” as separators and add it to thepathslist. - Recursively call
dfson the left child of the current node, passing the updated path. - Recursively call
dfson the right child of the current node, passing the updated path. - After exploring both children, backtrack by removing the last element from the
path(backtracking step). - Call the
dfsfunction starting with the root node and an empty path list. - Return the
pathslist 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.