Skip to main content

257. Binary Tree Paths

easy

Return every root-to-leaf path in a binary tree as 'a->b->c'-style strings. Two-line recursion plus a path accumulator — the simplest possible tree DFS enumeration template.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given the root of a binary tree, return all root-to-leaf paths in any order. A leaf is a node with no children.

Constraints

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

Examples

Example 1

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

Example 2

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Recurse DFS. Carry the current path as a list of strings (cheap to extend) or as a path-so-far string.

Hint 2

Leaf base case: !node.left and !node.right -> snapshot the path joined with '->'.

Hint 3

Recurse on each non-null child with the path extended by the child's value.

Hint 4

If using a mutable list, pop after recursing (backtrack).

Solution approach

Reveal approach

Recursive DFS. dfs(node, path): if node is null, return. Push node.val onto path. If node is a leaf, snapshot path.join('->') to result. Otherwise recurse into node.left and node.right. Pop on the way out so siblings see a clean path (backtracking). Alternative no-backtrack version: pass path strings by value — each recursive call gets a new string with the current node appended, no pop needed. The latter is slower because of string allocation but easier to reason about. Time is O(n^2) worst case (n paths of length up to n each, copying every char), or O(n * h) average; space is O(h) recursion depth plus O(n) for the path buffer.

Complexity

Time
O(n^2)
Space
O(h)

Related patterns

  • recursion
  • dfs
  • tree-traversal

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Apple
  • Microsoft

More Recursion practice problems

See all Recursion problems →