Reference: LeetCode Difficulty: Easy

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

Example:

1 2 3 4 5 6 7 Input: 1 / \ 2 3 \ 5 Output: ["1->2->5" , "1->3" ]

Analysis Methods:

The idea is similar to other sum problems.

Brute-Force
Time: $O(N + Lh)$ where $L$ is the number of leaves.
Space: $O(N + h) = O(N)$
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 private HashMap<TreeNode, TreeNode> map;private ArrayList<TreeNode> leaves;public List<String> binaryTreePaths (TreeNode root) { map = new HashMap <>(); leaves = new ArrayList <>(); findParentsAndLeaves(root, null ); ArrayList<String> result = new ArrayList <>(); for (TreeNode leaf : leaves) { StringBuffer bf = new StringBuffer (); TreeNode p = leaf; while (map.get(p) != null ) { bf.insert(0 , "->" + p.val); p = map.get(p); } bf.insert(0 , p.val); result.add(bf.toString()); } return result; } private void findParentsAndLeaves (TreeNode x, TreeNode parent) { if (x == null ) return ; if (x.left == null && x.right == null ) leaves.add(x); map.put(x, parent); findParentsAndLeaves(x.left, x); findParentsAndLeaves(x.right, x); }

Recursion Note:

Bad code: (Too many list operations)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 private void binaryTreePathsHelper (TreeNode x, LinkedList<String> result) { if (x == null ) return ; if (result.size() == 0 ) { result.add(x.val + "" ); } else { String str = result.removeLast(); result.add(str + "->" + x.val); } if (x.left == null && x.right == null ) return ; String newStr = "" ; boolean twoChildren = x.left != null && x.right != null ; if (twoChildren) { newStr = result.getLast() + "" ; } binaryTreePathsHelper(x.left, result); if (twoChildren) { result.addLast(newStr); } binaryTreePathsHelper(x.right, result); }

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`

.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 public List<String> binaryTreePaths (TreeNode root) { LinkedList<String> result = new LinkedList <>(); binaryTreePathsHelper(root, null , result); return result; } private void binaryTreePathsHelper (TreeNode x, String pathStr, LinkedList<String> result) { if (x == null ) return ; if (pathStr == null ) { pathStr = "" + x.val; } else { pathStr += "->" + x.val; } if (x.left == null && x.right == null ) { result.add(pathStr); return ; } binaryTreePathsHelper(x.left, pathStr, result); binaryTreePathsHelper(x.right, pathStr, result); }

More Improvement:

The idea is using `StringBuffer`

.
Use the method `setLength`

to cut the string.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 public List<String> binaryTreePaths (TreeNode root) { LinkedList<String> result = new LinkedList <>(); StringBuilder sb = new StringBuilder (); binaryTreePathsHelper(root, sb, result); return result; } private void binaryTreePathsHelper (TreeNode x, StringBuilder sb, LinkedList<String> result) { if (x == null ) return ; int oldLen = sb.length(); if (sb.length() == 0 ) { sb.append(x.val); } else { sb.append("->" + x.val); } if (x.left == null && x.right == null ) { result.add(sb.toString()); } else { binaryTreePathsHelper(x.left, sb, result); binaryTreePathsHelper(x.right, sb, result); } sb.setLength(oldLen); }