Binary Tree Paths

Problem

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

For example, given the following binary tree:

   1
 /   \
2     3
 \
  5
All root-to-leaf paths are:

["1->2->5", "1->3"]

Solution

Recursive Solution: String concatenation O(n) time

public class Solution {

    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        if (root != null) helper(res, root, "");
        return res;
    }

    private void helper(List<String> res, TreeNode node, String path) {
        if (node.left == null && node.right == null) {
            res.add(path + node.val);
            return;
        }
        if (node.left != null) helper(res, node.left, path + node.val + "->");
        if (node.right != null) helper(res, node.right, path + node.val + "->");
    }
}

Recursive Solution: StirngBuilder O(n) time and O(n) space

public class Solution {

    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        if (root != null) helper(res, root, sb);
        return res;
    }

    private void helper(List<String> res, TreeNode node, StringBuilder sb) {
        if (node == null) return;
        int len = sb.length();
        sb.append(node.val);
        if (node.left == null && node.right == null) res.add(sb.toString());
        else {
            sb.append("->");
            helper(res, node.left, sb);
            helper(res, node.right, sb);
        }
        sb.setLength(len);
    }
}

Analysis

This is a typical pre-order traversal problem
We need to get all the paths hence we need recursion to make it
The end of recursive method should bee when node.left == null && node.right == null
In that case, we add the current path to our res
If not, we add the current node.val and with "->"

String concatenation is really costly, therefore we should StringBuilder to get the path
In the second solution, we first append node.val to sb as long as the node != null
Before we adding though, we get the length of sb
This is because we need to update the path when we meet bifurcation
We should not include the other part of subtree nodes' values
At the end of function, we do sb.setLength() with the length we get at very beginning