Balanced Binary Tree

Problem statement

Given a binary tree, determine if it is height-balanced.(link)

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: true

Example 2:

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

Example 3:

Input: root = []
Output: true

Constraints:

• The number of nodes in the tree is in the range [0, 5000].

• -10<sup>4</sup> <= Node.val <= 10<sup>4</sup>

Solution

Brute Force Approach

Visit each node to compute the left and right heights. If the difference between them exceeds 1, return false immediately. To determine the tree's height, consult this article (link).

Time - O(n) x O(n!) -(derived easily using a skewed tree)

Space - O(n) - (Auxillary space)

class Solution {

    public int maxDepth(TreeNode root){
        if(root == null) return 0;

        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);

        return Math.max(leftDepth, rightDepth) +1;
    }

    public boolean isBalanced(TreeNode root) {
        if(root==null) return true;
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);

        if(Math.abs(leftHeight-rightHeight)>1) return false;

        if(!isBalanced(root.left) || !isBalanced(root.right)) return false;

        return true;
    }
}

Optimal Approach

Here, we make a slight adjustment to the calculation approach (link). The key step is to check the difference between the right and left heights; if it exceeds 1, we return -1 immediately. Additionally, if either the left or right height is -1, we also return -1. A return value of -1 indicates that the tree is not a binary tree. In all other cases, if the tree is balanced, we return the usual height.

Time - O(n)

Space - O(n) (Auxillary space)

class Solution {

    public int maxDepth(TreeNode root){
        if(root == null) return 0;

        int leftDepth = maxDepth(root.left);
        if(leftDepth==-1) return -1;

        int rightDepth = maxDepth(root.right);
        if(rightDepth==-1) return -1;

        if(Math.abs(leftDepth-rightDepth)>1) return -1;

        return Math.max(leftDepth, rightDepth) +1;
    }

    public boolean isBalanced(TreeNode root) {
        return maxDepth(root)!=-1;
    }
}