Free Trees lessonsTrees · Stage 3 · Paths · Step 2

List every route from the top

Write out every root-to-leaf path as text, by building the path string on the way down and saving it when a leaf is reached. About 14 minutes.

Build the route as you descend

A route is the list of values from the root down to a leaf, written with arrows between them. When you step from a node to a child, the child's route is the node's route, an arrow, and the child's value.

So pass the route so far as text. Each call adds its own value and passes the longer text to its children. The order of the answer follows the walk: the left subtree's routes first, then the right's.

Append your value: to the route passed in.

Add an arrow: before passing it to a child.

In code

path = prefix + str(node.val)
next_prefix = path + "->"

All routes in the tree 3, with 6 and 1 below it, and 5 and 8 under 6.

route: 3
saved: []

At 3, the route so far is 3. Go left first.

Move 1 of 5

Save at a leaf

A leaf is a node with no left and no right child. When you stand on one, the route text holds the complete path, so add it to the answer and return.

A node with only one child is not a leaf. It simply continues in the direction that exists. An empty tree has no routes at all, so return an empty list without starting the walk.

One child only: is not a leaf; keep going.

Empty tree: gives an empty list.

In code

routes = []
routes.append("1->2")
routes.append("1->3")    # one per leaf

Quick check

A node has a right child but no left child. What does the walk do?

AIt continues to the right child, since the node is not a leaf
BIt saves the route, because the left child is missing
CIt stops, since the tree is not balanced

Show the answer

It continues to the right child, since the node is not a leaf. Only a node with no children ends a route.

Your problem

Binary tree paths

Given the root of a binary tree, return all root-to-leaf paths as strings, in the order a left-to-right depth-first walk finds them. Write each path as its values joined by the arrow "->". An empty tree gives an empty list.

Example

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

0 ≤ number of nodes ≤ 100 · -100 ≤ node.val ≤ 100

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.