/**
 * https://leetcode.com/problems/balanced-binary-tree/
 * TIme O(N) | Space O(H)
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function(root) {
    const isBaseCase = root === null;
    if (isBaseCase) return true;
    if (!isAcceptableHeight(root)) return false;
    if (!isChildBalanced(root)) return false;

    return true;
}

const isChildBalanced = (root) => {
    const left = isBalanced(root.left);
    const right = isBalanced(root.right);

    return left && right
}

const isAcceptableHeight = (root) => {
    const left = getHeight(root.left);
    const right = getHeight(root.right);

    const difference = Math.abs(left - right);

    return difference <= 1;
}

const getHeight = (root) => {
    const isBaseCase = root === null;
    if (isBaseCase) return 0;

    return dfs(root);
}

var dfs = (root) => {
    const left = getHeight(root.left)
    const right = getHeight(root.right);

    const height = Math.max(left, right);

    return height + 1;
}

/**
 * https://leetcode.com/problems/balanced-binary-tree/
 * TIme O(N) | Space O(H)
 * @param {TreeNode} root
 * @return {boolean}
 */
 var isBalanced = function (root) {
    const [ _height, _isBalanced ] = isRootBalanced(root);

    return _isBalanced;
};

var isRootBalanced = (root) => {
    const isBaseCase = root === null
    if (isBaseCase) return [ -1, true ];

    return dfs(root)
}

var dfs = (root) => {
    const [ left, isLeftBalanced ] = isRootBalanced(root.left);
    const [ right, isRightBalanced ] = isRootBalanced(root.right);
    const [ height, difference ]  = [ Math.max(left, right), Math.abs(left - right) ];

    const isAcceptableHeight = difference <= 1;
    const _isBalanced = isLeftBalanced && isRightBalanced;

    const _isRootBalanced = _isBalanced && isAcceptableHeight;

    return [ (height + 1), _isRootBalanced ];
}