[Leetcode] 110. Balanced Binary Tree (retry)

https://leetcode.com/problems/balanced-binary-tree/description/

initial

I tried solving top down like calculating height with height as parameter in dfs and incrementing it along the height down.

but this approach also needs to pass roots left and right child and put all nodes into recursion cuz we are not just comparing root's left and right subtrees. We are comparing all possible subtrees for a given node

but it is n^2 time (inefficient)

class Solution {
    public boolean isBalanced(TreeNode root) {
        return isBalancedTopDown(root, 0);
    }

    // Top-down recursive function with depth as a parameter
    public boolean isBalancedTopDown(TreeNode node, int depth) {
        if (node == null) return true;

        int leftHeight = height(node.left, depth + 1);
        int rightHeight = height(node.right, depth + 1);

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

        // Check if left and right subtrees are also balanced
        return isBalancedTopDown(node.left, depth + 1) && isBalancedTopDown(node.right, depth + 1);
    }

    // This computes the height from the current node to leaf (bottom-up)
    public int height(TreeNode node, int depth) {
        if (node == null) return depth;
        return Math.max(height(node.left, depth + 1), height(node.right, depth + 1));
    }
}

sol

should do bottoms up where when u reach node should return 0 and build up the height along the way.

To make time efficient, when we meet a subtree earlier in the call stack far away from root, where subtrees height difference is greater than 1, we return -1, which recurs up the call stack

/**
 * 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 {
    public boolean isBalanced(TreeNode root) {
        return height(root) == -1 ? false:true;
    }

    public int height(TreeNode node){
        if(node==null) return 0;

        int left = height(node.left);
        if(left==-1) return -1;
        int right = height(node.right);
        if(right==-1) return -1;

        if(Math.abs(left-right)>1) return -1;
        return Math.max(left,right)+1;
    } 
}

complexity

n time
log n if balanced, n if skewed