This is perhaps a truly interesting and mind numbing aspect of Binary Trees. Note, I am not saying ‘Binary Search Tree’ but ‘Binary Trees’. If unsure of the differences they are explained here.

Ok, how do we determine if a binary tree is balanced? A tree is height-balanced (balanced) if the heights of the left and right subtrees of each node are within 1. Before we do that let’s look at some examples to make sure we get that definition.

**Perfectly Balanced:**

This is perfectly balanced as the right and left subtrees of any node are the same height.

**Height Balanced:**

Consider we label the last 2 leaves, C and D as height 0. They thus are ‘height balanced’. However when we review, B does not have a counter node, or a fellow pair if you would like to put it rather loosely. However going back to our definition of ‘balanced’, *A tree is height-balanced (balanced) if the heights of the left and right subtrees of each node are within 1. *Wallah! This is balanced.

**Not Balanced:**

Just for extra clarity, this is not balanced. Why? Just looking at node B alone will show you that this left child sub-tree does not have a right child (and no not C, as C equally needs it’s own to the left).

Ok now that we have some rules in place, here’s the code. I’ve included RSpec tests for extra clarity. The algorithm was taken from Cracking the Coding Interview which written in C++ and ported to Ruby.

**Spec File:**

def build_balanced_tree bst = Trees::BinarySearchTree.new bst.insert(50) #root bst.insert(40) # left bst.insert(39) # left of 40 bst.insert(41) # right of 40 bst.insert(60) # right bst.insert(59) # left of 60 bst.insert(61) # right of 60 bst end def build_unbalanced_tree bst = Trees::BinarySearchTree.new bst.insert(50) #root bst.insert(60) #right bst.insert(12) # left bst.insert(40) # right bst.insert(13) # left bst.insert(44) # right bst.insert(55) # right bst end # -- snip snip from Cracking the Coding Interview **great book** # The idea is very simple: the difference of min depth and max depth # should not exceed 1, since the difference of the min and the max depth # is the maximum distance difference possible in the tree. describe Trees::BalancedTree do before :each do @bst_balanced = build_balanced_tree @bst_unbalanced = build_unbalanced_tree @bst = Trees::BinarySearchTree.new end context 'is the tree balanced' do it 'should return true if tree is empty' do expect(Trees::BalancedTree.is_balanced?(@bst)).to be true end it 'should validate if tree is balanced' do bst = build_unbalanced_tree expect(Trees::BalancedTree.is_balanced?(@bst_balanced)).to be true end it 'should validate if the tree is unbalanced' do bst = build_unbalanced_tree expect(Trees::BalancedTree.is_balanced?(@bst_unbalanced)).to be false end end end

[Actual Code: (based on a prior article)

module Trees module BalancedTree def self.is_balanced?(tree) (max_depth(tree.root) - min_depth(tree.root) <= 1) end private def self.max_depth(tree) return 0 if ((not tree.respond_to? :left) or (not tree.respond_to? :right)) return 1 + [max_depth(tree.left), max_depth(tree.right)].max end def self.min_depth(tree) return 0 if ((not tree.respond_to? :left) or (not tree.respond_to? :right)) return 1 + [min_depth(tree.left), min_depth(tree.right)].min end end end

**References:**

- Images taken from these Lecture Notes