[DSA][Trees] Balanced Binary Tree

Leetcode 110

Given a binary tree, determine if it is height-balanced.
A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

[What can I ask?]
- Should an empty tree (i.e., when the root is None) be considered balanced?

[Key Idea]
- Use DFS to recursively determine the depth and whether the tree is balanced.

Get Woolaf's Techscope’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

[Solution 1] Depth First Search

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def dfs(node):
            if not node:
                return [True, 0]
            
            left, right = dfs(node.left), dfs(node.right)
            isBalanced = left[0] and right[0] and abs(left[1] - right[1]) <= 1
            return [isBalanced, 1 + max(left[1], right[1])]
        
        return dfs(root)[0]

To determine whether a tree is height-balanced, we need to compute the depth difference between the left and right subtrees at each node. To do this, we define a DFS function that recursively calculates the depth of the left and right subtrees, and returns False if the difference exceeds 1.

However, this means that the DFS function must return not only the depth of the current node but also whether the subtree rooted at that node is height-balanced. Therefore, we return a pair: [isBalanced, depth].

At each node, we use the depth and balance status returned from the left and right subtrees to check whether both are balanced and whether their depth difference is at most 1. If so, the current node is also balanced.

Furthermore, to improve efficiency, if either the left or right subtree is already unbalanced, we can immediately return False without further traversal, avoiding unnecessary computation.

⏱️ Time Complexity
This algorithm visits every node in the tree exactly once, so the time complexity is O(n), where n is the number of nodes in the tree.

🧠 Space Complexity
The space complexity is determined by the depth of the recursive call stack, which is proportional to O(h), where h is the height of the tree.
In the worst case (e.g., a skewed tree), the space complexity becomes O(n). On average (e.g., in a balanced tree), it is O(log n).