Diameter of Binary Tree

Problem

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

Intuition

The problem is to determine whether a binary tree is balanced or not. A balanced binary tree is defined as a tree in which the heights of the two subtrees of every node never differ by more than 1. The intuition is to perform a depth-first search (DFS) on the binary tree, calculating the height of each subtree at each step, and checking for balance conditions.

Approach

Depth-First Search (DFS):

Define a recursive DFS function that calculates the height of each subtree.
The base case is when the current node is None, in which case the height is 0.
Calculate the heights of the left and right subtrees using recursive calls.
Check for balance conditions:
If the height difference between the left and right subtrees is greater than 1, or if either subtree is unbalanced (indicated by a height of -1), return -1 to indicate imbalance.
Otherwise, return the height of the current subtree.
Return Result:

The final result is whether the height of the entire tree is -1 or not.

Complexity

• Time complexity:

The time complexity is O(n), where n is the number of nodes in the binary tree. Each node is visited exactly once during the traversal.

• Space complexity:

The space complexity is O(h), where h is the height of the binary tree. This is because the maximum depth of the recursion stack is equal to the height of the tree. In the average case, for a balanced binary tree, the height is O(log n), making the space complexity O(log n). However, in the worst case of an unbalanced tree, the height could be O(n), resulting in a space complexity of O(n). The space complexity is dominated by the depth of the recursive call stack.

Code

# 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: Optional[TreeNode]) -> bool:
        def dfs(root):
            if not root:
                return 0

            left = dfs(root.left)
            right = dfs(root.right)

            if left == -1 or right == -1 or abs(left - right) > 1:
                return -1

            return 1 + max(left , right)

        return dfs(root) != -1