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) =
7Returns (boolean)
trueExample 2
Input
tree (int[]) =
[1,2,2,3,3,0,0,4,4]size (int) =
9Returns (boolean)
falseExample 3
Input
tree (int[]) =
[]size (int) =
0Returns (boolean)
trueCalculate 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)Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run