Show problems as
Classic problem #257EasyStringBacktrackingTreeDepth-First SearchBinary Tree

Binary Tree Paths

Real-world version: Cave Routes to Every Dead End
Tracked in this browser only
Read Binary Tree Paths on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A caving club has surveyed a dry limestone system. One chamber is the entrance, and every chamber has at most two onward passages leading deeper, one that the surveyors call the left passage and one they call the right. No passage ever rejoins a chamber already visited, so the system branches and never closes a loop. Each chamber is stencilled with its floor height in metres relative to the water table, which may be negative.

The survey reaches you as chambers, listing the system one depth band at a time, left to right. Slot 0 holds the entrance. Every chamber in the listing claims the next two unclaimed slots for its passages, the left one first and the right one second. A slot holding null means no chamber hangs there, and such a slot claims no slots of its own. Trailing null slots may be left off the end of the listing.

A route starts at the entrance, follows onward passages, and finishes at a chamber with no onward passage at all. Write a route as the stencilled heights of the chambers it passes through, entrance first, joined by forward slashes, for example 12/-4/0.

Return every route in the system. The routes may come back in any order.

Examples

Example 1

Input
chambers = [0, -3, 7]
Output
["0/-3", "0/7"]

The entrance has both passages, and each leads straight to a chamber with nothing beyond it, so there are two routes of two chambers each.

Example 2

Input
chambers = [4, 2, null, 9]
Output
["4/2/9"]

The entrance has only a left passage, and the chamber it reaches has only a left passage of its own, so the single route runs three chambers deep.

Example 3

Input
chambers = [5]
Output
["5"]

The entrance is also a dead end, so the one route consists of it alone.

Example 4

Input
chambers = [8, 3, 10, 1, 6, null, 14, null, null, null, 7, 13]
Output
["8/3/1", "8/3/6/7", "8/10/14/13"]

Three chambers in this system have no onward passage, and each contributes the sequence of heights read from the entrance down to it.

Constraints

  • The number of surveyed chambers is in the range [1, 100].
  • -100 <= chambers[i] <= 100 for every slot that holds a chamber
  • chambers[0] holds a chamber
  • No slot in the listing follows a slot that holds null and was never claimed

The values you return may be in any order.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def binary_tree_paths(chambers: list[int | None]) -> list[str]:
Java
public List<String> binaryTreePaths(Integer[] chambers)

More on the same topics