110. Balanced Binary Tree

Problem Statement

Given a binary tree, determine if it is

height-balanced.

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].

• -104 <= Node.val <= 104

Intuition

Approach: 
Find height and take abs

Links

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

Video Links

Approach 1:

C++

class Solution {
public:

    int find_height(TreeNode *root){
        if(root == NULL)
            return 0;

        int l = find_height(root->left);   //Traverse Left
        if(l == -1) return -1;    
        // if from bottom recieves -1 (tree not balanced)

        int r = find_height(root->right);  //Traverse Right
        if(r == -1) return -1;

        if(abs(l-r) >1) return -1;     

        return 1+max(l,r);
    }

    bool isBalanced(TreeNode* root) {
        if(root==NULL)
            return true;
        return find_height(root) >= 1;
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Similar Problems