How do you approach Binary Tree Paths?

Carry the path built so far as you descend, and record it when you reach a node with no children.

What is the time complexity of Binary Tree Paths?

Time complexity: O(n * h) - each of up to O(n) paths costs O(h) to build.. Space complexity: O(h) for the recursion, plus the output..

What are common mistakes on Binary Tree Paths?

Handling the null node deep in the recursion instead of as the first base case. Returning early from a subtree when the answer needs both sides explored. Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.

gitGood.dev

← Back to problems

Binary Tree Paths

EasyData Structures

Description

Given a binary tree, return every **root-to-leaf** path as a string with values joined by `"->"`. Return the paths in left-to-right depth-first order. The tree is given as a **level-order array with explicit nulls**, where the children of index `i` sit at `2i + 1` and `2i + 2`. An empty array is an empty tree.

Example 1

Input: root = [1,2,3,null,5]

Output: ["1->2->5", "1->3"]

Example 2

Input: root = [1]

Output: ["1"]

Example 3

Input: root = [1,2]

Output: ["1->2"]

Constraints

- 1 <= number of nodes <= 100 - -100 <= Node.val <= 100 - Paths must be returned in left-to-right DFS order.

Binary Tree Paths: approach, complexity and pitfalls

An easy trees problem, graded against 6 test cases (3 of them hidden).

The pattern: Trees

Recursive traversal of binary trees and BSTs - depth, validation, and path problems.

Reach for it when you see: A TreeNode input, or anything about depth, ancestry, or in-order ordering.

More Treesproblems →

If you are stuck

Show the 3-step hint ladder

Carry the path built so far as you descend, and record it when you reach a node with no children.
Visit the left child before the right child - that is what produces the required ordering for free.
Either pass an immutable string down (simplest), or push/pop a shared array - the pop is the backtracking step people forget.

The optimal approach

Show the approach: DFS carrying state down, recording at the leaves

This is the introductory backtracking shape: build partial state on the way down, and commit it to the answer when a terminal condition is met - here, a node with no children.

Two ways to carry the path. Passing a string down means each call gets its own copy, so there is nothing to undo, and for trees of this size the copying cost is irrelevant. Passing a shared array avoids the copies but requires pushing before recursing and popping afterwards - and a missing pop is the classic backtracking bug, where later paths inherit fragments of earlier ones.

Ordering comes free from the traversal: recursing left before right yields exactly left-to-right DFS order, so no sorting is needed.

The leaf test is worth stating precisely - a node with no children at all, not a node with a missing left child. Treating a one-child node as a leaf would emit truncated paths and drop the real ones below it.

Time: O(n * h) - each of up to O(n) paths costs O(h) to build.
Space: O(h) for the recursion, plus the output.

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Null values. A null appears in the input. Guard your dereferences rather than relying on the shape of the sample case.

Common Trees mistakes

These apply to the pattern as a whole, not just this problem.

Handling the null node deep in the recursion instead of as the first base case.
Returning early from a subtree when the answer needs both sides explored.
Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.