EasyStringBacktrackingTreeDepth-First SearchBinary TreeUpdated Sep 2026

257. Binary Tree Paths

Asked at Capital One

Difficulty

Easy

Time

O(n * h)

Space

O(h)

Pattern

String

Companies

1

Problem

You are given the root of a binary tree. Return every path from the root down to a leaf, as a list of strings.

A leaf is a node that has no left child and no right child. A node with only one child is not a leaf, so a path never stops there. Each path is written with the node values joined by ->, for example "1->2->5". The paths may appear in any order.

If the tree is empty, return an empty list.

Only root-to-leaf paths count

2not a leaf5leaf → 1->2->513leaf → 1->3
Node 2 has a child, so it is not a leaf and 1->2 is not an answer.

Constraints

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

Examples

Example 1
Inputroot = [1,2,3,null,5]
Output["1->2->5","1->3"]
WhyNode 1 has two children. Going left leads to 2, and 2 has a right child 5, which is a leaf — so we record 1->2->5. Going right from 1 leads to 3, which has no children, so we record 1->3. Node 2 is not a leaf because it has a child, so 1->2 is not recorded.
Example 2
Inputroot = [1]
Output["1"]
WhyThe root is also the only leaf, so the single path is just "1".

Asked At

1 companies
CompanyDifficulty
Capital OneEasyView all Capital One questions →

How to Think About It

1

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.

2

DFS from the root, carrying the path built so far. When you reach a leaf, the path is complete — add it to the result.

3

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.

4

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"].

5

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.

DFS carrying the path so far

251path = "1"3Start at the root with an empty path, then append 12path = "1->2"5leaf → record "1->2->5"13Go left: append 2, then append 5 and record the path2513leaf → record "1->3"Back at the root, go right: append 3, a leaf, andrecord itpath = path + "->" + child.valleaf: no left and no rightresult = ["1->2->5", "1->3"]
Each call appends its own value. When a call lands on a leaf, the carried string is a finished path.
ComplexityTime O(n * h)Space O(h)Every node is visited once, but building each path string copies up to h characters, where h is the tree height.

What Trips People Up in Real Interviews

1

Recording a path at a null child instead of at a leaf. A node with one child would then produce an extra, incomplete path.

2

Sharing one mutable path list and forgetting to pop after the recursive call, so paths leak into each other.

3

Adding a trailing "->" to leaf paths. Add the arrow only when you are about to descend.

4

Not mentioning complexity honestly. String building makes it O(n * h), not O(n).

Solution Code

O(n * h) time
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 res

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(n * h) time and O(h) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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)`.