Check for balanced binary tree

Intuition

The reasoning behind checking if a binary tree is balanced revolves around ensuring that, for every node in the tree, the height difference between the left and right subtrees is no more than one. This condition prevents the tree from being skewed too much to one side, ensuring a balanced structure. By recursively assessing this balance condition at each node, it's possible to determine if the entire tree maintains a balanced state.

Approach

First, check if the root node is null. If it is, return true because an empty tree is inherently balanced.
For non-empty trees, recursively calculate the height of both the left and right subtrees using a helper function, often called getHeight. Store these heights and compare them. If the absolute difference between the heights is greater than 1, return false, as this indicates the tree is unbalanced at the current node.
If the height difference is 1 or less, proceed by recursively invoking the isBalanced function on the left and right child nodes. If both subtrees are found to be balanced, return true. If either subtree is unbalanced, return false, indicating that the tree overall is not balanced.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    bool isBalanced(TreeNode *root) {
        // If the tree is empty, it's balanced
        if (root == nullptr) {
            return true;
        }

        // Calculate the height of left and right subtrees
        int leftHeight = getHeight(root->left);
        int rightHeight = getHeight(root->right);

        // Check if the absolute difference in heights
        // of left and right subtrees is <= 1
        if (std::abs(leftHeight - rightHeight) <= 1 &&
            isBalanced(root->left) &&
            isBalanced(root->right)) {
            return true;
        }

        // If any condition fails, the tree is unbalanced
        return false;
    }

private:
    // Function to calculate the height of a subtree
    int getHeight(TreeNode *root) {
        // Base case: if the current node is NULL,
        // return 0 (height of an empty tree)
        if (root == nullptr) {
            return 0;
        }

        // Recursively calculate the height
        // of left and right subtrees
        int leftHeight = getHeight(root->left);
        int rightHeight = getHeight(root->right);

        // Return the maximum height of left and right subtrees
        // plus 1 (to account for the current node)
        return std::max(leftHeight, rightHeight) + 1;
    }
};

// Main function
int main() {
    // Creating a sample binary tree
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->left->right->right = new TreeNode(6);
    root->left->right->right->right = new TreeNode(7);

    // Creating an instance of the Solution class
    Solution solution;

    // Checking if the tree is balanced
    if (solution.isBalanced(root)) {
        std::cout << "The tree is balanced." << std::endl;
    } else {
        std::cout << "The tree is not balanced." << std::endl;
    }

    return 0;
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int data;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int val) { data = val; left = null; right = null; }
 * }
 **/

class Solution {
    public boolean isBalanced(TreeNode root) { 
        // If the tree is empty, it's balanced
        if (root == null) {
            return true;
        }

        // Calculate the height of left and right subtrees
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);

        // Check if the absolute difference in heights
        // of left and right subtrees is <= 1
        if (Math.abs(leftHeight - rightHeight) <= 1 &&
            isBalanced(root.left) &&
            isBalanced(root.right)) {
            return true;
        }

        // If any condition fails, the tree is unbalanced
        return false;
    }

    // Function to calculate the height of a subtree
    public int getHeight(TreeNode root) {
        // Base case: if the current node is NULL,
        // return 0 (height of an empty tree)
        if (root == null) {
            return 0;
        }

        // Recursively calculate the height
        // of left and right subtrees
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);

        // Return the maximum height of left and right subtrees
        // plus 1 (to account for the current node)
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

// Main function
public class Main {
    public static void main(String[] args) {
        // Creating a sample binary tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.left.right.right = new TreeNode(6);
        root.left.right.right.right = new TreeNode(7);

        // Creating an instance of the Solution class
        Solution solution = new Solution();

        // Checking if the tree is balanced
        if (solution.isBalanced(root)) {
            System.out.println("The tree is balanced.");
        } else {
            System.out.println("The tree is not balanced.");
        }
    }
}
# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution(object):
    def isBalanced(self, root):
        # If the tree is empty, it's balanced
        if root is None:
            return True

        # Calculate the height of left and right subtrees
        left_height = self.getHeight(root.left)
        right_height = self.getHeight(root.right)

        # Check if the absolute difference in heights
        # of left and right subtrees is <= 1
        if abs(left_height - right_height) <= 1 and \
           self.isBalanced(root.left) and \
           self.isBalanced(root.right):
            return True

        # If any condition fails, the tree is unbalanced
        return False

    def getHeight(self, root):
        # Base case: if the current node is NULL,
        # return 0 (height of an empty tree)
        if root is None:
            return 0

        # Recursively calculate the height
        # of left and right subtrees
        left_height = self.getHeight(root.left)
        right_height = self.getHeight(root.right)

        # Return the maximum height of left and right subtrees
        # plus 1 (to account for the current node)
        return max(left_height, right_height) + 1

# Main function
if __name__ == "__main__":
    # Creating a sample binary tree
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    root.left.right.right = TreeNode(6)
    root.left.right.right.right = TreeNode(7)

    # Creating an instance of the Solution class
    solution = Solution()

    # Checking if the tree is balanced
    if solution.isBalanced(root):
        print("The tree is balanced.")
    else:
        print("The tree is not balanced.")
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *      constructor(val = 0, left = null, right = null){
 *          this.data = val;
 *          this.left = left;
 *          this.right = right;
 *      }
 * }
 **/

class Solution {
    isBalanced(root) {
        // If the tree is empty, it's balanced
        if (root === null) {
            return true;
        }

        // Calculate the height of left and right subtrees
        let leftHeight = this.getHeight(root.left);
        let rightHeight = this.getHeight(root.right);

        // Check if the absolute difference in heights
        // of left and right subtrees is <= 1
        if (Math.abs(leftHeight - rightHeight) <= 1 &&
            this.isBalanced(root.left) &&
            this.isBalanced(root.right)) {
            return true;
        }

        // If any condition fails, the tree is unbalanced
        return false;
    }

    // Function to calculate the height of a subtree
    getHeight(root) {
        // Base case: if the current node is NULL,
        // return 0 (height of an empty tree)
        if (root === null) {
            return 0;
        }

        // Recursively calculate the height
        // of left and right subtrees
        let leftHeight = this.getHeight(root.left);
        let rightHeight = this.getHeight(root.right);

        // Return the maximum height of left and right subtrees
        // plus 1 (to account for the current node)
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

// Main function
(function main() {
    // Creating a sample binary tree
    let root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.right = new TreeNode(3);
    root.left.left = new TreeNode(4);
    root.left.right = new TreeNode(5);
    root.left.right.right = new TreeNode(6);
    root.left.right.right.right = new TreeNode(7);

    // Creating an instance of the Solution class
    let solution = new Solution();

    // Checking if the tree is balanced
    if (solution.isBalanced(root)) {
        console.log("The tree is balanced.");
    } else {
        console.log("The tree is not balanced.");
    }
})();

Complexity Analysis

Time Complexity: O(N^2) where N is the number of nodes in the Binary Tree. For each node in the Binary Tree, all other nodes are traversed to calculate its height, resulting in a nested traversal structure, leading to O(N) operations for each of the N nodes, hence O(N * N) = O(N^2).

Space Complexity: O(1) as no additional data structures or memory is allocated.

Intuition

The O(N*N) time complexity of the previous method can be improved by incorporating the balance check directly within the tree traversal process. Instead of recalculating the heights of the left and right subtrees at each node repeatedly, these heights can be determined in a bottom-up fashion via postorder traversal. This method allows for the efficient validation of balance conditions during traversal, minimizing redundant computations and enabling the early identification of unbalanced nodes.

Algorithm Steps

Perform a postorder traversal of the Binary Tree using recursion: First visit the left subtree, then the right subtree, and finally the root node. During this traversal, compute the heights of the left and right subtrees for each node. Utilize these computed heights to verify the balance condition at the current node.
If, at any node, the absolute difference between the heights of the left and right subtrees exceeds 1, or if any subtree is determined to be unbalanced (returns -1), return -1 immediately, signaling that the tree is unbalanced.
For a balanced tree, return the height of the current node by taking the greater height of its left or right subtree and adding 1 to account for the current node itself.
Continue the traversal process until all nodes have been visited. The final result will either be the height of the entire tree if it is balanced, or -1 if the tree is found to be unbalanced at any point.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    // Function to check if the tree is balanced
    bool isBalanced(TreeNode *root) {
        // Check if the tree's height difference
        // between subtrees is less than 2
        // If not, return false; otherwise, return true
        return dfsHeight(root) != -1;
    }

private:
    // Recursive function to calculate the height of the tree
    int dfsHeight(TreeNode *root) {
        // Base case: if the current node is NULL,
        // return 0 (height of an empty tree)
        if (root == nullptr) return 0;

        // Recursively calculate the height of the left subtree
        int leftHeight = dfsHeight(root->left);
        // If the left subtree is unbalanced,
        // propagate the unbalance status
        if (leftHeight == -1) return -1;

        // Recursively calculate the height of the right subtree
        int rightHeight = dfsHeight(root->right);
        // If the right subtree is unbalanced,
        // propagate the unbalance status
        if (rightHeight == -1) return -1;

        // Check if the difference in height between left and right subtrees is greater than 1
        // If it's greater, the tree is unbalanced,
        // return -1 to propagate the unbalance status
        if (std::abs(leftHeight - rightHeight) > 1) return -1;

        // Return the maximum height of left and right subtrees, adding 1 for the current node
        return std::max(leftHeight, rightHeight) + 1;
    }
};

// Main function
int main() {
    // Creating a sample binary tree
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->left->right->right = new TreeNode(6);
    root->left->right->right->right = new TreeNode(7);

    // Creating an instance of the Solution class
    Solution solution;

    // Checking if the tree is balanced
    if (solution.isBalanced(root)) {
        std::cout << "The tree is balanced." << std::endl;
    } else {
        std::cout << "The tree is not balanced." << std::endl;
    }

    return 0;
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int data;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int val) { data = val; left = null; right = null; }
 * }
 **/

class Solution {
    /**
     * Checks if the binary tree is balanced.
     * A binary tree is considered balanced if the height difference between
     * the left and right subtrees of every node is at most 1.
     * 
     * @param root The root node of the binary tree.
     * @return true if the tree is balanced, false otherwise.
     */
    public boolean isBalanced(TreeNode root) {
        // Call the recursive helper method to check balance status.
        // If the heightDifference() returns -1, the tree is unbalanced.
        return dfsHeight(root) != -1;
    }

    /**
     * Recursive method to calculate the height of the tree.
     * Returns -1 if the tree is unbalanced, otherwise returns the height of the tree.
     * 
     * @param root The current node of the tree.
     * @return The height of the tree if balanced, -1 if unbalanced.
     */
    private int dfsHeight(TreeNode root) {
        // Base case: If the current node is null, the height of an empty tree is 0.
        if (root == null) return 0;

        // Recursively calculate the height of the left subtree.
        int leftHeight = dfsHeight(root.left);
        // If the left subtree is unbalanced, propagate the unbalance status.
        if (leftHeight == -1) return -1;

        // Recursively calculate the height of the right subtree.
        int rightHeight = dfsHeight(root.right);
        // If the right subtree is unbalanced, propagate the unbalance status.
        if (rightHeight == -1) return -1;

        // Check if the difference in height between the left and right subtrees is greater than 1.
        // If the difference is greater, the tree is unbalanced.
        if (Math.abs(leftHeight - rightHeight) > 1) return -1;

        // Return the height of the tree rooted at the current node.
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

// Main class for testing the Solution class
public class Main {
    public static void main(String[] args) {
        // Creating a sample binary tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.left.right.right = new TreeNode(6);
        root.left.right.right.right = new TreeNode(7);

        // Creating an instance of the Solution class
        Solution solution = new Solution();

        // Checking if the tree is balanced
        if (solution.isBalanced(root)) {
            System.out.println("The tree is balanced.");
        } else {
            System.out.println("The tree is not balanced.");
        }
    }
}
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def isBalanced(self, root):
        # Function to check if the tree is balanced
        def dfsHeight(root):
            # Base case: if the current node is None,
            # return 0 (height of an empty tree)
            if not root:
                return 0

            # Recursively calculate the height of the left subtree
            leftHeight = dfsHeight(root.left)
            # If the left subtree is unbalanced,
            # propagate the unbalance status
            if leftHeight == -1:
                return -1

            # Recursively calculate the height of the right subtree
            rightHeight = dfsHeight(root.right)
            # If the right subtree is unbalanced,
            # propagate the unbalance status
            if rightHeight == -1:
                return -1

            # Check if the difference in height between left and right subtrees is greater than 1
            # If it's greater, the tree is unbalanced,
            # return -1 to propagate the unbalance status
            if abs(leftHeight - rightHeight) > 1:
                return -1

            # Return the maximum height of left and right subtrees, adding 1 for the current node
            return max(leftHeight, rightHeight) + 1

        # Check if the tree's height difference between subtrees is less than 2
        # If not, return False; otherwise, return True
        return dfsHeight(root) != -1

# Main function
if __name__ == "__main__":
    # Creating a sample binary tree
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    root.left.right.right = TreeNode(6)
    root.left.right.right.right = TreeNode(7)

    # Creating an instance of the Solution class
    solution = Solution()

    # Checking if the tree is balanced
    if solution.isBalanced(root):
        print("The tree is balanced.")
    else:
        print("The tree is not balanced.")
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *      constructor(val = 0, left = null, right = null) {
 *          this.data = val;
 *          this.left = left;
 *          this.right = right;
 *      }
 * }
 **/

class Solution {
    // Function to check if the tree is balanced
    isBalanced(root) {
        // Helper function to calculate the height of the tree
        const dfsHeight = (root) => {
            // Base case: if the current node is null,
            // return 0 (height of an empty tree)
            if (root === null) return 0;

            // Recursively calculate the height of the left subtree
            const leftHeight = dfsHeight(root.left);
            // If the left subtree is unbalanced,
            // propagate the unbalance status
            if (leftHeight === -1) return -1;

            // Recursively calculate the height of the right subtree
            const rightHeight = dfsHeight(root.right);
            // If the right subtree is unbalanced,
            // propagate the unbalance status
            if (rightHeight === -1) return -1;

            // Check if the difference in height between left and right subtrees is greater than 1
            // If it's greater, the tree is unbalanced,
            // return -1 to propagate the unbalance status
            if (Math.abs(leftHeight - rightHeight) > 1) return -1;

            // Return the maximum height of left and right subtrees, adding 1 for the current node
            return Math.max(leftHeight, rightHeight) + 1;
        }

        // Check if the tree's height difference between subtrees is less than 2
        // If not, return false; otherwise, return true
        return dfsHeight(root) !== -1;
    }
}

// Main function
function main() {
    // Creating a sample binary tree
    const root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.right = new TreeNode(3);
    root.left.left = new TreeNode(4);
    root.left.right = new TreeNode(5);
    root.left.right.right = new TreeNode(6);
    root.left.right.right.right = new TreeNode(7);

    // Creating an instance of the Solution class
    const solution = new Solution();

    // Checking if the tree is balanced
    if (solution.isBalanced(root)) {
        console.log("The tree is balanced.");
    } else {
        console.log("The tree is not balanced.");
    }
}

// Execute the main function
main();

Complexity Analysis

Time Complexity: O(N) where N is the number of nodes in the Binary Tree.

Space Complexity: O(1) as no additional data structures or memory is allocated.

Problem List

Check for balanced binary tree

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Intuition

Algorithm Steps

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code