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

  1. Images taken from these Lecture Notes

Leave a Reply

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