Java: Balanced Binary Tree

Thought Process

To determine if a binary tree is balanced, we can use a recursive approach. A tree is balanced if the height difference between the left and right subtrees of every node is at most '1'. We calculate the height of each subtree recursively and check if the absolute difference in heights exceeds '1'. If it does, the tree is unbalanced. This approach ensures that we traverse the tree efficiently while checking the balance condition. 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
 
class Solution {
    boolean isBalanced = true;
    int height(TreeNode root){

        if(root==null)
            return 0;

        int leftTree = height(root.left);
        int rightTree = height(root.right);

        if(Math.abs(leftTree-rightTree)>1)
            isBalanced = false;

        return 1 + Math.max(leftTree,rightTree);
    }
    public boolean isBalanced(TreeNode root) {
        
        if(root==null)
            return true;

        int x = height(root);
        return isBalanced;
    }
}

Code Complexity

Time Complexity: O(n)

The algorithm visits each node exactly once, where 'n' is the number of nodes in the tree.

Space Complexity: O(h)

The space used by the recursion stack depends on the height of the tree (h). In the worst case (a skewed tree), the space complexity is O(n).

Code copied!