# 257. Binary Tree Paths

Reference: LeetCode
Difficulty: Easy

## Problem

Given a binary tree, return all root-to-leaf paths.

Example:

## Analysis

Methods:

The idea is similar to other sum problems.

1. Brute-Force
• Time: $O(N + Lh)$ where $L$ is the number of leaves.
• Space: $O(N + h) = O(N)$
2. Recursion
• Use String concatenation.
• Time: $O(N^2)$
• Best: $O(N\log{N})$
• Worst: $O(N^2)$ when it is a long list.
• Space: $O(Lh)$. $L$ is the number of leaves / paths.
• Stack frame: $O(h)$
• result list: $O(Lh)$
• For a bushy tree: Number of leaves is $\sim \frac{N}{2}$, and the height is $\log{N}$. So the space is $O(N\log{N})$.
• For a spindly tree: Number of leaves is $\sim O(1)$, but the height is $N$. So the sapce is $O(N)$.
• If we use StringBuffer, we’ll gain $O(N)$ time complexity. Applying it is a bit tricky.
• Time: $O(N)$
• Space: $O(Lh)$

## Code

### Brute-Force

Note:

• Use StringBuffer for better performance.

### Recursion

Note:

Bad code: (Too many list operations)

Improvement:

• Pass the pathStr down by argument (by copy).
• Add only happens when it reaches a leaf node.
• Pass null first to handle special case for root.

More Improvement:

• The idea is using StringBuffer.
• Use the method setLength to cut the string.

Comment Junhao Wang
a software engineering cat