Адекватный ли код я пишу?

Вы придумали себе отличное упражнение и нашли способ его решить, за это вам твёрдая пять и респект.

Использование рекурсии для решение проблемы, это тоже отличный выбор когда дело касается работы с файловой системой.

На что можно обратить внимание. Первым делом: то что может жить вне функции - выносится за её пределы:

const promisifyReadDir = util.promisify((fs.readdir));
const promisifyStat = util.promisify((fs.stat));

эти переменные могут быть объявлены сразу после require. Обратите внимание: мы используем const по умолчанию всегда. И заменяем его на let только при острой необходимости. Это помогает вам и другим программистам понять, глядя на объявление переменной, что она будет меняться. Это поможет обратить на неё особое внимание.

Еще, мы можем модифицировать конечный результат отработки промиса, возвратив новое значение из функции then. Такое поведение называется chaining. Вот его пример:

promisifyStat(path)
  // Тут получаем наш stat, ничего необычного
  .then(stat => {
    // но мы можем вернуть новое значение из этой функции
    return stat.size;
  })
  // тут мы уже получаем только размер файла
  .then(size => {
    // далее мы опять можем что-то сделать с нашим размером и вернуть уже что-то новое
    return size < 1024
  })
  .then(isLessThanKilobyte => {
    return isLessThanKilobyte ? 'маленький файл' : 'большой файл';
  })
  .then(console.log); // в консоль будет падать строка 'маленький файл' или 'большой файл'

Более того, мы можем вернуть новый промис из then и конечный промис дождётся результата возвращённого промиса и только тогда зарезолвится. Такое поведение функции then называется flattening. Вот пример (слегка надуманный):

promisifyStat(path)
  .then(stat => {
    return new Promise((resolve) => {
      setTimeout(() => {
        resolve(stat.size);
      }, 1000);
    })
  })
  // Через секунду у нас вызовется этот колбэк и в него будет передано значение size
  .then(size => console.log(size));

Вот как можно решить задачу, использовав chaining и flattening:

const fs = require('fs');
const pathModule = require('path');
const util = require('util');
const promisifyReadDir = util.promisify(fs.readdir);
const promisifyStat = util.promisify(fs.stat);
const tree = (path, result = { directories: [], files: [] }) => (
    promisifyReadDir(path)
    // Получаем список файлов
        .then(files =>
            // Уплощаем сбор статистики по файлам
            Promise.all(
                files.map(file =>
                    // Получаем статистику для каждого файла из списка
                    promisifyStat(pathModule.join(path, file))
                    // собрав статистику для каждого файла, возвращаем объект, содержащий имя файла и его статистику
                    // нам это пригодится на следующем шаге
                        .then(stat => ({ file, stat })),
                ),
            ),
        )
    // Вот тут к нам приезжает уже сформированный массив файлов вместе со статистикой для текущей папки
        .then(filesWithStats =>
            // [1] Уплощаем это дело
            Promise.all(
                filesWithStats.map(({ file, stat }) => {
                    // Начиная отсюда мы имеем имя файла и можем проверить
                    // файл ли это или директория
                    if (stat.isFile()) {
                        result.files.push(file);
                        return result;
                    }
                    result.directories.push(file);
                    // [2] Повторяем процедуру в случае если мы встретили директорию
                    return tree(pathModule.join(path, file), result);
                }),
            ),
        )
    // Благодаря тому что мы уплощали [2] через Promise.all [1],
    // это then будет вызван только в тот момент когда вся работа по сбору всех подпапок будет выполнена
        .then(() => result)
);
tree('node_modules').then(console.log);

Код выше имеет несколько недостатков:

1. Этот код сведёт с ума программиста, который не слышал про flattening в промисах и мало сталкивался с элементами функционального программирования в JS.
2. Этот код нарушает один из принципов функционального программирования: он мутирует объект result (почитайте про мутации объектов в JS когда появится время и желание, это полезная тема для размышлений). Мутации происходят через вызов методов push у массивов файлов и директорий. Обычно это усложняет понимание кода и делает его не совсем адекватным. Пример неадекватности текущего кода - последний then не оперирует входным параметром коллбека, а просто возвращает result как есть.

С первым пунктом тяжело помочь, а второй можно исправить:

const fs = require('fs');
const pathModule = require('path');
const util = require('util');
const promisifyReadDir = util.promisify(fs.readdir);
const promisifyStat = util.promisify(fs.stat);
const tree = (path, result = { directories: [], files: [] }) =>
    promisifyReadDir(path)
        .then(files =>
            Promise.all(
                files.map(file =>
                    promisifyStat(pathModule.join(path, file)).then(stat => ({ file, stat })),
                ),
            ),
        )
        .then(filesWithStats =>
            Promise.all(
                filesWithStats.map(({ file, stat }) => {
                    if (stat.isFile()) {
                        return {
                            ...result,
                            files: result.files.concat(file),
                        };
                    }
                    return tree(pathModule.join(path, file)).then(res => ({
                        ...res,
                        directories: res.directories.concat(file),
                    }));
                }),
            ),
        )
        // Вот тут к нам приехжает массив массив статистики по корневой директории и по всем поддирукториям корневой директории
        // в виде [{directories: [], files: ['rootfile1', 'rootfile2']}, {directories: ['directory1'], files: ['directory1file1', 'directory1file2']}, {directories: ['directory2'], files: ['directory2file3', 'directory2file3']}
        // Функцией reduce мы склеим то что было воедино и вернём уже готовый резульат
        .then(stats =>
            stats.reduce(
                (acc, pathStat) => ({
                    directories: acc.directories.concat(pathStat.directories),
                    files: acc.files.concat(pathStat.files),
                }),
                { directories: [], files: [] },
            ),
        );
tree('node_modules').then(console.log);

Замечание первое. Промисы - это хорошо, но в 2019м году пора уже использовать async-await. Вот заготовка для кода:

async function tree(path) {
    const files = await promisifyReadDir(path);
    const items = await Promise.all(files.map(async file => {
        const stats = promisifyStat(file);
        if (stats.isDirectory()) {
            const subtree = await tree(file);
            const result = ...;
            return {
                folders: [ result, ...subtree.folders ],
                files: subtree.files,
            };
        }
        const result = ...;
        return {
            folders: [],
            files: [ result ],
        };
    }));
    return {
        folders: [].concat(...items.map(x => x.folders)),
        files: [].concat(...items.map(x => x.files)),
    };
}

Обратите внимание, что ни разу не пришлось вызывать у промиса метод then.

Также обратите внимание на паттерн await Promise.all(files.map(async => ...)) - таким образом можно распараллелить поток (flow, не путать с thread) управления.

Замечание второе. Тренировка в использовании промисов - это хорошо, но вообще-то жёсткие диски слабо предназначены для параллельной работы. Вполне возможно, что тот же самый код, написанный в последовательном стиле (с циклами вместо Promise.all) мог бы даже работать быстрее. И уж совершенно точно, что последовательный код будет менее требователен к системным ресурсам. Попробуйте написать такой код сами, он куда проще параллельного варианта.

С другой стороны, параллельный вариант кода хорошо подходит для обхода сетевых директорий - ведь там основные лаги вызваны сетью, а не жёстким диском.