Trees, Recursion
A tree is balanced if 1) the depths of its child trees differ by no more than one and 2) this is true for EVERY subtree.
Here’s an example of a balanced tree:
This is also a balanced tree — there’s more on the big left trunk, but the heights vary by only one:
Here’s an imbalanced tree — the heights vary by too much (the left-hand child of the root has two levels of descendants, whereas the right-hand child has zero levels):
In this exercise, you’ll make a function that tests where a binary tree is balanced.
We’ve defined a class, BinaryNode:
class BinaryNode(object):
"""Node in a binary tree."""
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def is_balanced(self):
"""Is the tree at this node balanced?"""
If you run checkbalanced.py, the tests. Implement the check_balanced function.