Balanced Binary Tree

To solve this coding challenge, we need to determine if a given binary tree is height-balanced. A binary tree is considered height-balanced if and only if the heights of the two child subtrees of any node differ by no more than one. Also, both subtrees themselves need to be balanced. We'll utilize a depth-first search (DFS) approach, where for each node we recursively check the height of the left and right subtrees, and evaluate if the current node is balanced based on these heights.

Explanation

In a height-balanced binary tree:

1. The difference between the heights of the left and right subtrees for every node is at most 1.
2. Both the left subtree and the right subtree must also be balanced.
To achieve this, we will use a helper function called
check_height
. This function will:
3. Return the height of the tree if it is balanced.
4. Return -1 if the tree (or subtree) is not balanced.
We start by checking the root of the binary tree and recursively assess the left and right subtrees. During this process, we:
5. Check the height of the left and right subtrees.
6. If the height difference between the left and right subtrees of any node is more than 1, we immediately conclude that the tree is not balanced.
7. If the subtree itself is not balanced (indicated by a height of -1), we propagate this information back up the call stack.

                                            
# Pseudocode with comments

# Function to determine if the binary tree is balanced
function is_balanced(root):
# Helper function to check the height of a node
function check_height(node):
# Base case: if node is None, it's height is 0
if node is None:
return 0

# Recursively check the height of the left subtree
left_height = check_height(node.left)
# If left subtree is not balanced, propagate the -1 result
if left_height == -1:
return -1

# Recursively check the height of the right subtree
right_height = check_height(node.right)
# If right subtree is not balanced, propagate the -1 result
if right_height == -1:
return -1

# If the current node is imbalanced
if abs(left_height - right_height) > 1:
return -1

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

# Call the helper function on the root and check if it returns -1
return check_height(root) != -1

                                        

Detailed Steps in Pseudocode

8. Define the main function
   is_balanced
   that takes
   root
   as a parameter.
9. Define a helper function
   check_height
   inside
   is_balanced
   . This function should take
   node
   as a parameter and return its height if balanced, otherwise return -1.
10. Inside
    check_height
    :
• Check if the
  node
  is
  None
  . If so, return height 0.
• Recursively call
  check_height
  on the
  left
  child of the node and store the result in
  left_height
  .
• If
  left_height
  is -1, return -1 to indicate imbalance.
• Recursively call
  check_height
  on the
  right
  child of the node and store the result in
  right_height
  .
• If
  right_height
  is -1, return -1 to indicate imbalance.
• Check if the absolute difference between
  left_height
  and
  right_height
  is greater than 1.
• If so, return -1 to indicate the current node is imbalanced.
• Otherwise, return the maximum of
  left_height
  and
  right_height
  plus 1 to account for the current node.
11. In
    is_balanced
    , call
    check_height
    with the
    root
    node and check if the result is not equal to -1.
12. Return the result of the above condition. If true, the tree is balanced; otherwise, it is not.

This approach ensures that we balance-check each node in the tree efficiently, leveraging recursion and the principles of depth-first search.