Close Menu
    Code and Debug
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook X (Twitter) Instagram YouTube WhatsApp
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook Instagram YouTube LinkedIn WhatsApp
    Code and Debug – BlogCode and Debug – Blog
    Code and Debug – BlogCode and Debug – Blog
    Home»Data Structures & Algorithms»Balanced Binary Tree | Leetcode 110 | Optimal and Slightly Optimal Solutions
    Data Structures & Algorithms

    Balanced Binary Tree | Leetcode 110 | Optimal and Slightly Optimal Solutions

    codeanddebugBy codeanddebug1 September 2025No Comments3 Mins Read
    Share Facebook Twitter Pinterest LinkedIn Tumblr Reddit Telegram Email
    Featured image of a question to solve Balanced Binary Tree
    Share
    Facebook Twitter LinkedIn Pinterest Email

    You are given the root of a binary tree. Your task is to determine whether the tree is height-balanced.

    A binary tree is considered height-balanced if, for every node in the tree:

    • The height difference between its left and right subtrees is at most 1.
    • Both left and right subtrees are also height-balanced.

    Here’s the [Problem Link] to begin with.

    Example 1

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

    Example 2

    Input: root = [1,2,2,3,3,null,null,4,4]
    
            1
           / \
          2   2
         / \
        3   3
       / \
      4   4
    
    Output: false
    Explanation: The left subtree has height 3 more than the right subtree, so it is unbalanced.

    Intuition and Approach

    To check if a tree is balanced:

    1. Compute the height of left and right subtrees for each node.
    2. If the absolute difference of heights is greater than 1, the tree is not balanced.
    3. To make this efficient, use a special return value -1 to signal imbalance. This allows early termination, avoiding unnecessary work.

    We’ll look at two versions:

    • Optimal solution – Computes left and right heights, then checks balance.
    • Slightly optimal solution – Adds a pruning step by checking left first, and only if it is balanced proceeds to check right.

    Optimal Solution

    Code Implementation

    class Solution:
        def solve(self, node):
            if node is None:
                return 0
            leftH = self.solve(node.left)
            rightH = self.solve(node.right)
            if leftH == -1 or rightH == -1:
                return -1
            if abs(leftH - rightH) > 1:
                return -1
            return 1 + max(leftH, rightH)
    
        def isBalanced(self, root: Optional[TreeNode]) -> bool:
            height = self.solve(root)
            if height == -1:
                return False
            return True

    Code Explanation

    • Base case: If the node is None, its height is 0.
    • Recursively compute leftH and rightH.
    • If either subtree is unbalanced (returns -1), propagate -1 upwards.
    • If the absolute difference of leftH and rightH exceeds 1, return -1 to mark unbalance.
    • Otherwise, return the actual height 1 + max(leftH, rightH).
    • isBalanced(root) checks the root result. If -1, return False, else return True.

    Slightly Optimal Solution

    Code Implementation

    class Solution:
        def solve(self, node):
            if node is None:
                return 0
            leftH = self.solve(node.left)
            if leftH == -1:
                return -1
            rightH = self.solve(node.right)
            if rightH == -1:
                return -1
            if abs(leftH - rightH) > 1:
                return -1
            return 1 + max(leftH, rightH)
    
        def isBalanced(self, root: Optional[TreeNode]) -> bool:
            height = self.solve(root)
            if height == -1:
                return False
            return True

    Code Explanation

    • This version prunes earlier.
    • If the left subtree is already unbalanced (-1), it does not bother computing the right subtree.
    • Similarly, if the right is unbalanced, it exits early.
    • This saves unnecessary recursive calls when imbalance is found in large trees.

    Time and Space Complexity

    • Time Complexity (both versions):
      Each node is visited once, and at each node we do constant work.
      So time is O(N), where N is the number of nodes.
    • Space Complexity:
      The space is due to recursion depth. In the worst case (skewed tree), it can be O(N).
      In the best case (balanced tree), it is O(log N).

    Conclusion

    The Balanced Binary Tree problem is solved by combining height calculation with an early unbalance detection mechanism:

    • The optimal solution calculates both left and right subtree heights first.
    • The slightly optimal solution improves efficiency by pruning unnecessary checks as soon as imbalance is detected.

    Both approaches run in O(N) time and ensure early stopping when imbalance is found, making them efficient in practice.


    Join our Advance DSA COURSE

    For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.

    Binary Trees Easy
    Share. Facebook Twitter Pinterest LinkedIn Tumblr Email
    Previous ArticleBest Time to Buy and Sell Stock IV | Leetcode 188 | Recursion to Tabulation Approach
    Next Article Binary Tree Maximum Path Sum | Leetcode 124 | Detailed Recursive Solution
    codeanddebug
    • Website

    Related Posts

    Data Structures & Algorithms

    Symmetric Tree | Leetcode 101 | Recursive DFS Approach

    2 September 2025
    Data Structures & Algorithms

    Binary Tree Right Side View | Leetcode 199 | BFS and DFS Approaches

    2 September 2025
    Data Structures & Algorithms

    Bottom View of Binary Tree | BFS with Horizontal Distance Mapping

    2 September 2025
    Add A Comment
    Leave A Reply Cancel Reply

    Categories
    • Data Structures & Algorithms (240)
      • Beginner (82)
      • Expert (52)
      • Intermediate (106)
    • Uncategorised (1)
    Recent Posts

    Symmetric Tree | Leetcode 101 | Recursive DFS Approach

    2 September 2025

    Binary Tree Right Side View | Leetcode 199 | BFS and DFS Approaches

    2 September 2025

    Bottom View of Binary Tree | BFS with Horizontal Distance Mapping

    2 September 2025

    Top View of Binary Tree | BFS with Horizontal Distance Mapping

    2 September 2025

    Vertical Order Traversal of a Binary Tree | Leetcode 987 | BFS + Sorting Solution

    2 September 2025
    Facebook Instagram YouTube LinkedIn WhatsApp
    © 2025 Code and Debug. All rights reserved.

    Type above and press Enter to search. Press Esc to cancel.