Check Tree Balance: Solution

Problem: Check Tree Balance
Challenge: Medium
Concepts: Trees, Recursion
Download: check-balanced-solution.zip

A good solution follows:

class BinaryNode(object):   # ...
    def is_balanced(self):
        """Is the tree at this node balanced?"""

        # START SOLUTION

        def _num_descendants(node):
            """Returns number of descendants or None if already imbalanced."""

            if not node:
                # Our base case: we're not a real node (child of a leaf)
                return 0

            # Get descendants on left; if "None", already imbalanced---bail out
            left = _num_descendants(node.left)

            if left is None:
                return None

            # Get descendants on right; if "None", already imbalanced---bail out
            right = _num_descendants(node.right)

            if right is None:
                return None

            if abs(left - right) > 1:
                # Heights vary by more than 1 -- imbalanced!
                return None

            # Height of this node is height of our deepest descendant + ourselves
            return max(left, right) + 1

        return _num_descendants(self) is not None

Nested Function Declaration

Our provided solution uses a “nested function declaration” — _num_descendants is defined inside of is_balanced.

This is legal and sometimes a tidy way to structure code.

_num_descendants needs to be a separate method, as it calls itself recursively. We could have defined it outside of is_balanced and called it in the usual way (self._num_descendants(...)).

By defining it inside of is_balanced, we’re communicating that, as a function, it isn’t meant to be used except by is_balanced—and, in fact, isn’t usable outside of that outer method, since only is_balanced has access to _num_descendants.

When you define an inner function like this, it has access to the variables in the outer function—though we’re not taking advantage of that capability in this particular solution (nor would it benefit us, there are no useful variables defined in is_balanced).

On an advanced, separate note, when an inner function does use the variables of the outer function and returns access to the outer function, this creates what is called a “closure”—an intermediate programming construct that, while not related to this example, may be worth studying separately.

Exception-Based

In the provided solution, we pass None up to signal that the tree is not balanced. An alternate solution would be to raise an exception, which could be caught in is_balanced.

So, inside of _num_descendants, that would look like:

# Get descendants on left (might raise Exception)
left = _num_descendants(node.left)

# Get descendants on right (might raise Exception)
right = _num_descendants(node.right)

if abs(left - right) > 1:
    # Heights vary by more than 1 -- imbalanced!
    raise ValueError()

Then, the body of is_balanced becomes:

try:
    _num_descendants(self)
    return True
except ValueError:
    return False

The core idea of both solutions works the same. This second one is a little shorter and shows off the way that good use of exceptions and exception handling can make control flow a bit simpler.