Hackbright Code Challenges

Check Tree Balance

Check Tree Balance

Challenge

Medium

Concepts

Trees, Recursion

Download

check-balanced.zip

Solution

Check Tree Balance: Solution


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:

digraph bst { rankdir=TB 4-> 2; 4 -> NULLNULLNU [style=invis]; 4 -> 6; 2 -> 1; 2 -> X [style=invis]; 2 -> 3; 6 -> 5; 6 -> Y [style=invis]; 6 -> 7; NULLNULLNU [style=invis] X [style=invis] Y [style=invis] 1 [label="Node"]; 2 [label="Node"]; 3 [label="Node"]; 4 [label="Node"]; 5 [label="Node"]; 6 [label="Node"]; 7 [label="Node"]; }

This is also a balanced tree — there’s more on the big left trunk, but the heights vary by only one:

digraph bst { rankdir=TB 4-> 2; 4 -> NULLNULLNU [style=invis]; 4 -> 6; 2 -> 1; 2 -> X [style=invis]; 2 -> 3; 1 [label="Node"]; 2 [label="Node"]; 3 [label="Node"]; 4 [label="Node"]; 6 [label="Node"]; NULLNULLNU [style=invis] X [style=invis] }

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):

digraph bst { rankdir=TB 4-> 2; 4 -> NULLNULLNU [style=invis]; 2 -> 1; 2 -> X [style=invis]; 2 -> 3; 1 [label="Node"]; 2 [label="Node"]; 3 [label="Node"]; 4 [label="Node"]; NULLNULLNU [style=invis] X [style=invis] }

In this exercise, you’ll make a function that tests where a binary tree is balanced.

We’ve defined a class, BinaryNode:

checkbalanced.py
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.