function recursiveUpdateTree(treeObj, root) {
            var recurPromises = [];
            var toRemove = {}, toUpdate = {}, treeInfo;

            // We will first recur into sub-directories of root, then we'll handle
            // files
            _.each(root, function(val) {
                if (!val.file && val.fullPath) { // It's a dir
                    recurPromises.push(recursiveUpdateTree(treeObj, val));
                }
            });
            var madeChanges = false;
            var fullPath = "/" + root.fullPath;
            return Promise.all(recurPromises).then(function(recurResults) {
                // At this point all sub-directories trees have been recreated,
                // let's see if that changed anything
                recurResults.forEach(function(r) {
                    if (r.madeChanges) {
                        madeChanges = true;
                    }
                });
                // Let's now rebuild based on locally changed files
                // Did this directory exist before (last commit)?
                if (treeObj[fullPath]) {
                    // Lookup the sha of the old tree
                    var baseTree = treeObj[fullPath].sha;
                    // Let's iterate over all files in our change set
                    _.each(root, function(val) {
                        if (val.file) { // It's a file
                            if (val.file.status === "deleted") { // to delete
                                toRemove[pathUtil.filename(val.file.id)] = val.file;
                            } else {
                                toUpdate[pathUtil.filename(val.file.id)] = val.file;
                            }
                        }
                    });
                    // Let's first fetch the base tree for this dir
                    return githubCall("GET", "/repos/" + repo + "/git/trees/" + baseTree);
                } else {
                    // New directory, so we can add all files to the toUpdate object
                    _.each(root, function(val) {
                        if (val.file) { // It's a file
                            toUpdate[pathUtil.filename(val.file.id)] = val.file;
                        }
                    });
                    // and the previous version of this tree (which didn't exist) is empty
                    return {
                        tree: []
                    };
                }
            }).then(function(treeInfo_) {
                treeInfo = treeInfo_;

                // Post blobs for all updated files to Github
                var createBlobPromises = [];
                _.each(toUpdate, function(file) {
                    createBlobPromises.push(githubCall("POST", "/repos/" + repo + "/git/blobs", {}, {
                        encoding: "base64",
                        content: file.content
                    }).then(function(blobInfo) {
                        // Let's store the new sha in the file for convenience
                        file.sha = blobInfo.sha;
                    }));
                });
                return Promise.all(createBlobPromises);
            }).then(function() {
                var tree = treeInfo.tree;
                var seenPaths = {};

                // Now we add, change and remove from the old version of the tree (that we fetched from github)
                for (var i = 0; i < tree.length; i++) {
                    var treeItem = tree[i];
                    var fullTreeItemPath = "/" + (root.fullPath ? root.fullPath + "/" : "") + treeItem.path;
                    seenPaths[fullTreeItemPath] = true;
                    if (toRemove[treeItem.path]) {
                        // File got removed, let's remove it from the tree
                        tree.splice(i, 1);
                        i--;
                        madeChanges = true;
                    } else if (toUpdate[treeItem.path]) {
                        // File was changed, let's update its hash to the new blob hash
                        var obj = toUpdate[treeItem.path];
                        treeItem.sha = obj.sha;
                        // Delete from object to know which ones were updates and which were new blobs
                        delete toUpdate[treeItem.path];
                        madeChanges = true;
                    } else if (treeItem.type === "tree" && treeObj[fullTreeItemPath].sha !== treeItem.sha) {
                        // A subtree (sub-directory) was changed, let's update the hash in the tree
                        madeChanges = true;
                        if (treeObj[fullTreeItemPath].sha === null) {
                            // in fact, the tree was removed alltogether, so let's remove it from the tree
                            tree.splice(i, 1);
                            i--;
                        } else {
                            treeItem.sha = treeObj[fullTreeItemPath].sha;
                        }
                    }
                }
                // Let's find newly defined directories
                _.each(root, function(file, relativePath) {
                    if (file.fullPath && !file.file && !seenPaths[file.fullPath] && treeObj["/" + file.fullPath].sha) {
                        tree.push({
                            path: relativePath,
                            mode: "040000", // tree
                            type: "tree",
                            sha: treeObj["/" + file.fullPath].sha
                        });
                    }
                });

                // Finally, let's add all newly defined files to the tree
                // only newly defined files are left, because updated ones were removed earlier
                _.each(toUpdate, function(obj) {
                    madeChanges = true;
                    tree.push({
                        path: pathUtil.filename(obj.id),
                        mode: "100644",
                        type: "blob",
                        sha: obj.sha
                    });
                });

                if (tree.length === 0) {
                    return null;
                }
                if (madeChanges) {
                    // Something changed so let's actually create the new tree
                    console.log("Making a new tree:", fullPath);
                    return githubCall("POST", "/repos/" + repo + "/git/trees", {}, {
                        tree: tree
                    });
                } else {
                    // No changes made, let's use the old tree
                    return treeInfo;
                }
            }).then(function(newTreeInfo) {
                if (!newTreeInfo) {
                    // Tree was deleted
                    treeObj[fullPath].sha = null;
                    return {
                        madeChanges: true
                    };
                } else {
                    // Updating our cache
                    if (treeObj[fullPath]) {
                        treeObj[fullPath].sha = newTreeInfo.sha;
                    } else { // New directory
                        treeObj[fullPath] = {
                            sha: newTreeInfo.sha
                        };
                    }
                    return {
                        madeChanges: madeChanges,
                        sha: newTreeInfo.sha
                    };
                }
            }).
            catch (function(err) {
                if (err.message !== "exit") {
                    throw err;
                }
            });
        }
This function recursively recreates the tree structure bottom-up
It's kind of convoluted and probably needs to be cleaned up,
it seems to work just fine, though.

@param treeObj treeCache.files, that is: a /full/file/path -> info map
@param root the current subdirectory to hande in the change tree (as pulled out the db)