> Interview Breeze

Determine if a Tree is Height Balanced

Problem

For a given binary tree, determine whether it is height balanced, where height balanced is defined as a tree in which the absolute difference between the heights of the left and right sub-trees is no greater than 1. For this problem, you may use the following Binary Tree class:

class BinaryTreeNode():
    def __init__(self, value, left, right):
        self.value = value
        self.left= left
        self.right= right

Linear time solution

It is possible to solve this problem in linear time. We can calculate the height of the tree from the bottom nodes, and also pass a balanced boolean down the call stack as well. We check the heights of the two sub trees, and pass up the greater height between the left and right sub trees to the parent node. If anywhere along the way, the difference between to sub tree heights is too great, we set our balanced boolean to false. Since we also bubble up and check our balanced booleans, any parent tree will be marked as unbalanced as well.

def _is_height_balanced(tree_node, balanced = True):
    if tree_node is None: return (0, balanced)
    left_height, lb = _is_height_balanced(tree_node.left, balanced)
    right_height, rb = _is_height_balanced(tree_node.right, balanced)
    return (
        max(left_height, right_height) + 1, # max height
        lb and rb and (abs(left_height - right_height) <= 1) # sub trees are balanced?
    )

Though the function above does solve the problem, it returns a tuple and isn't super clean, so we can clean it up a bit by adding a helper function:

def is_height_balanced(tree_node):
    return _is_height_balanced(tree_node)[1]

You may also want to read:

Depth First Search

Depth first search (sometimes referred to as DFS) is an algorithm for traversing a graph or tree.

Read More >>
Binary Tree Column Printer

Given binary tree, write a function to print its values in column order, from the bottom to top. You can assume that there will be no collisions, in which 2 nodes would occupy the same row and column.

Read More >>
How to Implement a Quadtree in Python

A Quadtree is a data structure that allows two dimensional data, such as images or matrices, to be represented and traversed as a tree.

Read More >>

Python Console