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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Binary Tree Paths and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →