Binary Tree Paths
Asked at Capital One
Problem
Binary Tree Paths asks for every root-to-leaf path in a binary tree, formatted like "1->2->5". It is a straightforward DFS question that checks whether you can carry state down a recursion and recognize a leaf correctly.
Asked At
| Company | Difficulty | |
|---|---|---|
| Capital One | Easy | View all Capital One questions → |
How to Think About It
A path ends only at a leaf — a node with no left and no right child. A node with one child is not the end of a path.
DFS from the root, carrying the path built so far. When you reach a leaf, the path is complete — add it to the result.
Passing a new string (path + "->" + val) to each call keeps backtracking automatic, because each call has its own copy. With a shared list you must pop after returning.
Walkthrough for [1,2,3,null,5]: 1 -> go left 1->2 -> go right 1->2->5 (leaf, record). Back to 1, go right 1->3 (leaf, record). Result ["1->2->5","1->3"].
Edge cases: a single node returns ["1"]; negative values print with their minus sign.
Optimal Approach
Step 1: If root is null, return [].
Step 2: dfs(node, path):
path = path + str(node.val)
If node is a leaf: append path to the result and return.
Otherwise recurse into each non-null child with path + "->".
Step 3: Call dfs(root, "") and return the result.
Every node is visited once, but copying the path string costs up to O(h) per leaf.
Time: O(n * h). Space: O(h) recursion plus the output.
What Trips People Up in Real Interviews
Recording a path at a null child instead of at a leaf. A node with one child would then produce an extra, incomplete path.
Sharing one mutable path list and forgetting to pop after the recursive call, so paths leak into each other.
Adding a trailing "->" to leaf paths. Add the arrow only when you are about to descend.
Not mentioning complexity honestly. String building makes it O(n * h), not O(n).
Solution Code
def binaryTreePaths(root):
res = []
def dfs(node, path):
path += str(node.val)
if not node.left and not node.right:
res.append(path)
return
if node.left:
dfs(node.left, path + '->')
if node.right:
dfs(node.right, path + '->')
if root:
dfs(root, '')
return resFrequently Asked Questions
What is the Binary Tree Paths problem?
Binary Tree Paths asks for every root-to-leaf path in a binary tree, formatted like `"1->2->5"`. It is a straightforward DFS question that checks whether you can carry state down a recursion and recognize a leaf correctly.
How do you solve Binary Tree Paths?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Binary Tree Paths?
Binary Tree Paths is asked at Capital One. It is a easy difficulty problem.
What are common mistakes on Binary Tree Paths?
- Recording a path at a null child instead of at a leaf. A node with one child would then produce an extra, incomplete path.
- Sharing one mutable path list and forgetting to pop after the recursive call, so paths leak into each other.
- Adding a trailing `"->"` to leaf paths. Add the arrow only when you are about to descend.
- Not mentioning complexity honestly. String building makes it `O(n * h)`, not `O(n)`.