Determine if a binary tree is balanced

Question

I'm currently running through some Cracking the Coding Interview questions and my solution to 4-4 is quite different from any of the given solutions.

The question asks to determine if a given binary tree is balanced; more specifically, if the difference between the maximum and minimum depths within the tree is less than or equal to 1.

public static bool IsBalanced(Node node)
{
    var mm = new DepthMinMax();
    mm.Min = int.MaxValue;
    mm.Max = int.MinValue;

    FindMinMax(mm, node, 0);

    return (mm.Max - mm.Min <= 1) ? true : false;
}

private static void FindMinMax(DepthMinMax mm, Node node, int depth)
{
    if (node == null) return;

    FindMinMax(mm, node.L, depth + 1);
    FindMinMax(mm, node.R, depth + 1);

    // At a terminating node
    if (node.L == null || node.R == null)
    {
        if (mm.Min > depth) mm.Min = depth;
        if (mm.Max < depth) mm.Max = depth;
    }
}

public class Node
{
    public Node L { get; set; }
    public Node R { get; set; }
}

public class DepthMinMax
{
    public int Min { get; set; }
    public int Max { get; set; }
}

This works for my test cases, but they were far from exhaustive and I can't really conclude if my solution works for all cases / is efficient. My solution feels far too simple, which leads me to believe I've missed some kind of gotcha.

Answer 1

Came across this post as I was answering the same question in this book. My approach was also similar in solving this. I will post what I found as an answer since I cannot comment.

First, I think the or condition for checking the terminating node is incorrect. It should be a and condition to my understanding. I think we need to identify whether the current node is a leaf node before updating depths. For the following tree this would give a max depth of 3 and min depth of 1, which is incorrect. I did this in C++ as shown below.

      5
     /  \
    4    7
   /    / \
  1    6   8 
 /
0  


 void FindMinMax(int &min,int &max,Node *np,int height)
 {
     if(np==NULL) return;
     FindMinMax(min,max,np->left,height+1);
     FindMinMax(min,max,np->right,height+1);

     if(np->left==NULL || np->right==NULL)
     {
         if(min>height) min = height;
         if(max<height) max = height;
     }
 }

Second, I am not sure whether there are differences in the versions. In my book the question 4.1 is about checking whether a binary tree is balanced. This is defined as

heights of the two subtrees of any node never differ by more than one

If this is the requirement I think this algorithm won't work. Check the first two answers of this question. I think this algorithms checks whether the difference between farthest and closest leaves from root differ by more than one.

Edit: Here I assumed min max corresponds to maximum and minimum depths to leaf nodes.

Answer 2

One quick note, the line:

return (mm.Max - mm.Min <= 1) ? true : false;

is simplified to:

return (mm.Max - mm.Min) <= 1;

as it is already a Boolean expression.

Answer 3

From the interviewer point of view, this is what I would pay most of attention to:

• Comments not needed

  A comment explains a code which is not self explanatory. Every time you want to write a comment, take a second look - maybe there is a way to express your intentions better.

      // At a terminating node
      if (node.L == null || node.R == null)
  

  is a good example. If you feel the condition is not clear, give it a good name, and delete the comment:

      if (node.is_leaf())
  

• Algorithm

  If the left subtree is imbalanced it makes no sense to inspect the right subtree. A solution not addressing this observation is not a solution.

Answer 4

Some notes on the algorithm used.

Conceptually speaking your solution is not the most efficient. Your solution takes the definition of a balanced tree and implements it verbatim by computing the depth of each leaf, the minimum and maximum of those depths.

I propose a better solution found by negating the definition: a balanced tree is not an imbalanced tree. An imbalanced tree is a tree where there exist 2 leaves that have a bigger depth difference than 1. If the tree is balanced, you still have to check all the leaf nodes, but if it is imbalanced, more often than not this algorithm will end sooner because you can stop once you found the 2 leaves with a bigger depth difference.

Let's talk about the way you iterate over the nodes in order to find the leaves. What you implemented is a DFS (depth-first search) iteration. You scour down a path until you find a leaf node, then gradually come back up the tree checking the remaining branches. Using a BFS (breadth-first search) you have a much better chance of iterating over fewer nodes until you find the imbalance. This kind of search is better suited for this particular problem because it iterates over all the nodes at a particular depth.

The revised algorithm iterates over the nodes at each depth. Once you find a leaf node, you need to finish the depth you are on and iterate over the next depth with a different goal: if at this next depth you find a node that is not a leaf, the tree is imbalanced, otherwise it is balanced.