Balanced Binary Tree

Clarify the problem:

• The problem requires determining whether a binary tree is balanced.
• We need to check if the heights of the left and right subtrees of any node in the binary tree differ by at most one.
• We should return a boolean value indicating whether the binary tree is balanced or not.

Analyze the problem:

• Input: The root node of a binary tree.
• Output: A boolean value indicating whether the binary tree is balanced or not.
• Constraints:
  • The binary tree may be empty.
  • The binary tree may have any number of nodes.
  • The nodes in the binary tree may have arbitrary values.

Design an algorithm:

• We can use a recursive approach to check if the binary tree is balanced.
• We can define a recursive function called isBalanced that takes a node as input and returns a tuple of two values:
  • The height of the subtree rooted at the given node.
  • A boolean value indicating whether the subtree rooted at the given node is balanced or not.
• In the isBalanced function, we can calculate the height of the left subtree and the height of the right subtree recursively.
• If the absolute difference between the heights of the left and right subtrees is greater than one, we return False for the balance status.
• If both the left and right subtrees are balanced and their heights differ by at most one, we return True for the balance status.
• We can use these values to check the balance status of the current node and propagate it upwards in the recursive calls.

Explain your approach:

• We will implement a function called isBalanced that takes the root node of a binary tree as input and returns a boolean value indicating whether the binary tree is balanced or not.
• The isBalanced function will be a recursive function that calculates the height and balance status of each subtree rooted at a given node.
• We will define a helper function called getHeight that calculates the height of a subtree rooted at a given node.
• In the isBalanced function, we will check if the absolute difference between the heights of the left and right subtrees is greater than one.
• We will also make recursive calls to check the balance status of the left and right subtrees.
• Finally, we will return the overall balance status based on the conditions mentioned above.

Write clean and readable code:

python

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def getHeight(node):
    if node is None:
        return 0
    return max(getHeight(node.left), getHeight(node.right)) + 1

def isBalanced(root):
    if root is None:
        return True

    left_height = getHeight(root.left)
    right_height = getHeight(root.right)

    if abs(left_height - right_height) > 1:
        return False

    return isBalanced(root.left) and isBalanced(root.right)

Test your code:

• To test the code, we can create binary trees with different structures and call the isBalanced function on them.
• Test case 1: Balanced binary tree

python

# Unbalanced binary tree
#        1
#       / \
#      2   3
#     /     \
#    4       5
#   /
#  6
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.left.left = TreeNode(6)
root.right.right = TreeNode(5)
print(isBalanced(root))  # Output: False

Optimize if necessary:

• The provided implementation has a time complexity of O(n^2) in the worst case, where n is the number of nodes in the binary tree.
• This is because for each node, we calculate the height of its left and right subtrees recursively, resulting in redundant calculations.
• To optimize the solution, we can modify the getHeight function to return -1 if a subtree is unbalanced. This will allow us to avoid redundant calculations by terminating early when we detect an unbalanced subtree.

python

def getHeight(node):
    if node is None:
        return 0

    left_height = getHeight(node.left)
    if left_height == -1:
        return -1

    right_height = getHeight(node.right)
    if right_height == -1:
        return -1

    if abs(left_height - right_height) > 1:
        return -1

    return max(left_height, right_height) + 1

def isBalanced(root):
    return getHeight(root) != -1

• This optimized approach has a time complexity of O(n), where n is the number of nodes in the binary tree, as we avoid redundant calculations.

Handle error cases:

• The code handles the case when the binary tree is empty by checking if the root node is None.
• In such a case, we return True to indicate that an empty tree is considered balanced.

Discuss complexity analysis:

• Time complexity: The optimized algorithm has a time complexity of O(n), where n is the number of nodes in the binary tree. This is because we visit each node once and perform a constant amount of work for each node.
• Space complexity: The space complexity is O(h), where h is the height of the binary tree. In the worst case, when the binary tree is highly unbalanced, the space complexity is O(n), as the recursion stack can grow up to the number of nodes in the tree. However, in the best case, when the binary tree is perfectly balanced, the space complexity is O(log n), where log n is the height of the tree.