Binary Tree Paths

Question (LC.257)

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

Example

I: [1,2,3,null,4,5]
O: ["1->2->4", "1->3->5"]
I: []
O: []

Bottom-up D&C

We want to try D&C when possible. It is always easier to implement because we only need to take care of the backtrack (postorder merge) part. We want the left child to report all the paths from itself to its leaves. We want to the right child to do the same task. Then we can process each report by append the root to all the paths. Base case? 1. leaf return itself 2. incomplete branch add nothing

// the report type is fine we can just use it
// recursive definition report all paths from yourself to your leaves  
public List<String> binaryTreePaths(TreeNode root) {
    List<String> currentPaths = new ArrayList<>();
    // base
    if (root == null) {
        return currentPaths;
    }
    if (root.left == null && root.right == null) {
        currentPaths.add(Integer.toString(root.val));
    }
    // divide
    List<String> leftPaths = binaryTreePaths(root.left);
    List<String> rightPaths = binaryTreePaths(root.right);    
    // merge
    for (String path : leftPaths) {
        currentPaths.add(root.val + "->" + path);
    }
    for (String path : rightPaths) {
        currentPaths.add(root.val + "->" + path);
    }
    return currentPaths;
}

Top-down Traverse

We want to do a preorder traversal from the root and to all the leaves. We want to append the root value during the previsit and remove the root value and "->" during postvisit. The base cases (stop conditions) are the same. 1. leaf node we want to only append the root value 2. incomplete branch just return

public List<String> binaryTreePaths(TreeNode root) {
    List<String> paths = new ArrayList<>();
    StringBuilder path = new StringBuilder();
    traverseHelper(paths, root, path);
    return paths;
}

// traverse all nodes preorder
private void traverseHelper(List<String> paths, TreeNode root, StringBuilder path) {
    // base 1. incomplete branch 2. leaf
    if (root == null) {
        return;
    }
    String rootStr = Integer.toString(root.val);
    if (root.left == null && root.right == null) {
        path.append(rootStr);
        paths.add(path.toString());
        path.delete(path.length() - rootStr.length(), path.length());
        return;
    }
    // traverse
    path.append(rootStr);
    path.append("->");
    traverseHelper(paths, root.left, path);
    path.delete(path.length() - (rootStr.length() + 2), path.length());

    path.append(rootStr);
    path.append("->");
    traverseHelper(paths, root.right, path);
    path.delete(path.length() - (rootStr.length() + 2), path.length());
}

As expected, traversing the tree is a lot harder to write because we need to take care of previsit and backtracking.