How would you determine if a binary tree is balanced?

Balancing a binary tree often refers to ensuring that the depth of the left and right subtrees of every node differs by at most 1.

To determine if a binary tree is balanced, you could use a depth-first search (DFS) strategy. To implement this, you’ll post-order traverse through the tree. For each node, you compute the heights of its left and right subtrees. If the difference in heights is more than 1, then the tree is not balanced.

Here’s the pseudocode of this approach:

define function isBalanced(tree) {
   return (height(tree) != -1)
}

define function height(node) {
  if (is_empty(node)) { 
    return 0
  }

  leftHeight = height(node.left)
  if (leftHeight == -1){
    return -1 
  }

  rightHeight = height(node.right)
  if (rightHeight == -1) {
    return -1
  }
 
  if (abs(leftHeight - rightHeight) > 1) {
    return -1
  } else {
    return max(leftHeight, rightHeight) + 1
  }
}

The ‘height‘ function returns -1 if the tree is unbalanced. Inside the ‘isBalanced‘ function, we check if the height function returns -1. If it returns -1, then the tree is unbalanced, and the ‘isBalanced‘ function returns False. If the height function doesn’t return -1, then the tree is balanced, and the ‘isBalanced‘ function returns True.

Finally, note that in the worst-case scenario, this algorithm has to traverse through all nodes of the tree, so its time complexity is O(n), where n is the number of nodes in the tree. This is the most efficient approach for this problem since any algorithm will have to visit all nodes at least once.

Note: This code assumes that an empty tree is balanced and that the height of an empty tree is 0. In some contexts, this may not be the desired definition. Be sure to clarify these points with your interviewer.