Tree Binary Tree Binary Search Tree Breadth First Search Depth First Search
Intermediate Level

Implement the balancedBinaryTreeCheck method that checks whether a binary tree is height-balanced.

The input contains a binary tree represented as an integer array tree in level-order format.

Your task is to check whether the tree is height-balanced. A binary tree is balanced when, for every node, the heights of the left and right subtrees differ by at most 1.

An empty tree is considered balanced.

Example 1
Input:
tree (int[]) = [3,9,20,0,0,15,7]
size (int) = 7
Return:
(boolean) true
Example 2
Input:
tree (int[]) = [1,2,2,3,3,0,0,4,4]
size (int) = 9
Return:
(boolean) false
Example 3
Input:
tree (int[]) = []
size (int) = 0
Return:
(boolean) true

Calculate the height of each subtree using depth-first search.

While calculating heights, also check the balance condition. If any subtree is already unbalanced, return a special value such as -1 and stop further normal height calculation.

If the root height calculation does not return -1, the whole tree is balanced.

Pseudocode:

function balancedBinaryTreeCheck(tree, size):
    return checkHeight(0) != -1
function checkHeight(index):
    if index >= size or tree[index] is missing:
        return 0
    leftHeight = checkHeight(2 * index + 1)
    if leftHeight == -1:
        return -1
    rightHeight = checkHeight(2 * index + 2)
    if rightHeight == -1:
        return -1
    if absolute(leftHeight - rightHeight) > 1:
        return -1
    return 1 + max(leftHeight, rightHeight)
Run your code to see the result.