Binary Tree: Is it balanced?

Balanced tree

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:

Perfect balance

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

Height Balanced:

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:

Un balanced tree

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 =
  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

def build_unbalanced_tree
  bst =
  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

# -- 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 =

  context 'is the tree balanced' do
    it 'should return true if tree is empty' do
      expect(Trees::BalancedTree.is_balanced?(@bst)).to be true

    it 'should validate if tree is balanced' do
      bst = build_unbalanced_tree
      expect(Trees::BalancedTree.is_balanced?(@bst_balanced)).to be true

    it 'should validate if the tree is unbalanced' do
      bst = build_unbalanced_tree
     expect(Trees::BalancedTree.is_balanced?(@bst_unbalanced)).to be false

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

    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

    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


  1. Images taken from these Lecture Notes

Leave a Reply

Your email address will not be published. Required fields are marked *