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);
}