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.

  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.
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<>();
// find child-parent mapping and all leaves
findParentsAndLeaves(root, null);
// construct path
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); // add the root
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); // leaves

map.put(x, parent); // child-parent mapping

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;

// update pathStr
if (pathStr == null) { // root case
pathStr = "" + x.val;
} else {
pathStr += "->" + x.val;
}

if (x.left == null && x.right == null) {
result.add(pathStr); // reach the root
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(); // for cutting the Stringbuilder when this node is traversed

// update StringBuilder
if (sb.length() == 0) { // root case
sb.append(x.val);
} else {
sb.append("->" + x.val);
}

if (x.left == null && x.right == null) {
result.add(sb.toString()); // reach the root
} else {
binaryTreePathsHelper(x.left, sb, result);
binaryTreePathsHelper(x.right, sb, result);
}

sb.setLength(oldLen);
}

Comment