Balanced Binary Tree | Neetcode

Given a binary tree, return true if it is height-balanced and false otherwise.

A height-balanced binary tree is defined as a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Example 1:

Input: root = [1,2,3,null,null,4]
Output: true

Example 2:

Input: root = [1,2,3,null,null,4,null,5]
Output: falseExample

To find our answer we need to first evaluate at a given node:

In which the left and right subtrees of every node differ in height by no more than 1.

Meaning at each node: Tree is not balanced if

Math.abs(leftNodeHeight - rightNodeHeight) > 1

we can conclude:

1. We need to calculate height.
2. How do we calculate the height?

A simple function to calculate height at any node is:

function height(node){
 if(!node){
   return 0
 }
 let leftNodeHeight  = height(node.left)
 let rightNodeHeight = height(node.right)

 return 1 + Math.max(leftNodeHeight, rightNodeHeight)
}

This is a simple function that calculate the height, now we need to determine at every node if it's left node tree is valid and right node tree is valid.

Valid in a sense the difference is no greater than 1.

if(Math.abs(leftNodeHeight - rightNodeHeight) > 1){
// return invalid represented by -1
return -1
}

function height(node){
 if(!node){
   return 0
 }
 let leftNodeHeight  = height(node.left)
 let rightNodeHeight = height(node.right)
 if(Math.abs(leftNodeHeight - rightNodeHeight) > 1){
  return -1
 }
 return 1 + Math.max(leftNodeHeight, rightNodeHeight)
}

return height(root) !== -1 

this is a simple code that says if a tree is balanced or not.