/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
// O(N^2) time
var isBalanced = function(root) {
 const maxHeight = (root) => {
   if (root === null) {
     return 0;
   }
   // Get the max height of the left subtree
   const leftHeight = maxHeight(root.left);
         
   // Get the max height of the right subtree
   const rightHeight = maxHeight(root.right);
   
   // Get the max between the two subtrees plus 1 to take into account the extra level
   return Math.max(leftHeight, rightHeight) + 1;
 }
 
 if (root === null) {
   return true;
 }
 
 // Get the max height of the left and right subtrees
 const leftHeight = maxHeight(root.left);
 const rightHeight = maxHeight(root.right);
 
 // Difference between two subtrees should be at most 1 and then we recursively check the left and right subtrees are balanced as well
 return Math.abs(leftHeight - rightHeight) <= 1 && isBalanced(root.left) && isBalanced(root.right);
};